题目描述

给你一棵 $n$ 个节点且带点权的树，$m$ 个询问，每个询问给你多条链，请你输出这几条链的点的集合并的颜色数 和 $mex$。

强制在线。

$1≤n≤10^5,1≤m≤3×10^4$。

$mex$ 就是一个集合中最小的没有出现的非负整数，注意 $0$ 要算。

比如说集合是1,9,2,6,0,8,1,7，则出现了0,1,2,6,7,8,9这7种不同的点权，因为没有3所以mex是3

输入格式

第一行三个数n，m，意义如题所述，和一个数f

如果f是0，代表Deus没有使用膜法，如果f是1，代表Deus使用了膜法

之后一行n个数，表示点权

之后n-1行，每行两个数x，y，表示x和y节点之间有一条边，保证是一个树

之后m行，每行先是一个数a，表示这次输入a条链，紧接着2a个数(x1,y1)(x2,y2)...表示每条树链

如果数据被Deus施了膜法，这2a个数都要异或上上一个询问的答案lastans，如果是第一次询问则这个lastans = 0，因为每次询问有两个答案，lastans为这两个答案的和

如果没有膜法，则-1s并且不异或

输出格式

m行，每行两个数表示点权种类数以及mex

输入输出样例 #1

输入 #1

10 1 0
0 0 0 1 1 0 2 2 1 2 
2 3
1 2
4 5
3 4
7 8
6 7
5 6
9 10
8 9
1
6 8

输出 #1

2 1

输入输出样例 #2

输入 #2

10 1 1
0 0 1 0 0 2 2 0 0 0 
2 3
1 2
4 5
3 4
7 8
6 7
5 6
9 10
8 9
4
1 7
3 3
1 1
9 3

输出 #2

3 3

说明/提示

设a的和为q

对于20%的数据，n,q<=1000，f=0

对于另外30%的数据，n,q<=100000，树是一条链，f=0

对于所有数据n,q<=100000,且点权<=30000

最后，由乃祝大家新年快乐