Tree Path Queries: Distinct Weights and MEX

You are given a tree with n nodes. Each node has an integer weight. There are m queries. In each query, you are given several chains (paths) in the tree. For each query, you must take the union of all nodes lying on any of the given chains, and then determine:

• The number of distinct node weights in the union set.
• The mex of the set of node weights. Here, mex is defined as the smallest nonnegative integer that does not appear in the set. In other words, if \(S\) is the set of node weights, then \[ \operatorname{mex}(S)=\min\{x\in \mathbb{Z}_{\ge 0}: x \notin S\} \] (note that \(0\) is considered a nonnegative integer).

For example, if the union set of weights is \(\{1, 9, 2, 6, 0, 8, 1, 7\}\), then the distinct weights are \(\{0, 1, 2, 6, 7, 8, 9\}\). There are 7 distinct weights and since 3 is missing, \(\operatorname{mex}(\cdot)=3\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of nodes and \(m\) is the number of queries.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) where \(w_i\) is the weight of the \(i\)-th node.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\) (the tree is undirected).

Then follow \(m\) queries. Each query starts with an integer \(k\) (the number of chains in this query). Then \(k\) lines follow, each containing two integers \(u\) and \(v\) representing the endpoints of a chain in the tree. The chain is defined as the simple path connecting nodes \(u\) and \(v\).

outputFormat

For each query, output two integers separated by a space:

• The number of distinct node weights in the union of all chains.
• The mex of the union of node weights.

Output the answers for each query on a new line.

sample

5 2
2 0 1 3 2
1 2
1 3
3 4
3 5
1
2 4
2
4 5
2 3

4 4
4 4