Description

Given a tree with n nodes. Each node has a weight. There are m queries. For each query, you are given multiple paths. Consider the union of these paths, and ask:

• how many distinct node weights appear, and
• the mex of those weights.

The mex of a set is the smallest non-negative integer that does not appear; note that 0 counts.

For example, if the set is 1, 9, 2, 6, 0, 8, 1, 7, then the distinct weights that appear are 0, 1, 2, 6, 7, 8, 9 (7 kinds). Since 3 does not appear, the mex is 3.

Input Format

• The first line contains three integers n and m as described above, and an integer f.
  • If f = 0, it means Deus did not use magic.
  • If f = 1, it means Deus used magic.
• The second line contains n integers, the node weights.
• The next n − 1 lines each contain two integers x and y, indicating there is an edge between nodes x and y. It is guaranteed to be a tree.
• The next m lines each describe a query:
  • Each line starts with an integer a, the number of paths in this query.
  • Then follow 2a integers representing the a pairs (x1, y1) (x2, y2) ... corresponding to the paths.
  • If the testdata has been blessed by Deus’s magic (f = 1), then all these 2a integers must be xor-ed with the previous query’s answer lastans. For the first query, lastans = 0. Since each query has two answers, lastans is the sum of those two answers.
  • If there is no magic (f = 0), then −1 s and do not xor.

Output Format

Output m lines. Each line contains two integers: the number of distinct node weights and the mex.

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

2 1

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

3 3

Hint

Let the sum of all a over all queries be q.

Constraints:

• For 20% of the testdata: n, q ≤ 1000, f = 0.
• For an additional 30% of the testdata: n, q ≤ 100000, the tree is a path, f = 0.
• For all testdata: n, q ≤ 100000, and node weights ≤ 30000.

Finally, Yuno wishes everyone a Happy New Year.

Translated by ChatGPT 5