K. ANDtreew
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Andrew was gifted a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$ and $$$q$$$ queries to answer. Each query consists of an integer $$$k$$$ between $$$1$$$ and $$$n$$$, inclusive, and $$$k$$$ different integers $$$x_1, x_2, \ldots, x_k$$$, each $$$x_i$$$ denoting the node numbered $$$x_i$$$.

The score of a forest is defined as the bitwise AND of the minimum values from each tree in the forest. After each query, Andrew's task was to print the maximum score of a forest obtained by removing some, possibly none, of the nodes given in the query. The score of an empty forest is $$$0$$$. When a node is removed, so are all the edges incident to it.

Andrew said that the problem was trivial and that he didn't want it, so he has now given it to you. Because you don't want to offend Andrew, you must now solve the problem.

Note: If you don't understand some graph theory terminology such as tree or forest, you can read about it from here.

Input

The first line contains a single integer $$$t$$$, the number of test cases. ($$$1 \le t \le 10$$$).

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ denoting the number of nodes and queries, respectively. ($$$1 \le n, q \le 5 \cdot 10^5$$$).

Then follow $$$n-1$$$ lines, each consisting of two integers $$$u$$$ and $$$v$$$, meaning that there is an edge between nodes $$$u$$$ and $$$v$$$. ($$$1 \le u, v \le n$$$; $$$u \neq v$$$). It is guaranteed that the edges form a tree.

Then follow $$$q$$$ lines, each containing an integer $$$k_i$$$ followed by $$$k_i$$$ integers $$$x_1 \lt x_2 \lt \ldots \lt x_{k_i}$$$, the nodes that can be removed in that query. ($$$1 \le k_i \le n$$$).

Additionally, it is guaranteed that the sum of $$$n$$$ and the sum of all $$$k_i$$$ over all test cases is at most $$$5 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1 - 10$$$ satisfy $$$q \leq 5$$$.

Output

For each query, print a single integer denoting the maximum score of a forest that Andrew can obtain.

Examples
Input
1
7 5
1 5
1 3
1 7
5 6
5 2
5 4
3 2 3 4
1 1
3 1 2 3
5 1 2 4 5 6
4 1 2 3 4
Output
1
2
4
3
5
Input
1
7 7
5 3
3 6
6 1
1 7
7 2
2 4
1 1
2 1 2
3 1 2 3
4 1 2 3 4
5 1 2 3 4 5
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7
Output
2
2
4
4
6
7
7
Note

 —

Problem Idea: Esomer

Problem Preparation: Esomer

Occurrences: Advanced 11