We have a tree with $n$ vertices, where vertex $1$ is the root. There are $q$ queries, and each query consists of a list of $k$ vertices: $u_1, u_2, ..., u_k$. The goal is to choose two vertices from each query in such a way that their Lowest Common Ancestor (LCA) is as close to the root as possible.
### Input
- The first line contains two integer $n,q$.
- The next $n - 1$ lines, each containing two integers $u,v$, there is an edge between $u$ and $v$.
- The next $q$ lines, each line is a query. The first integer in each query is the size $k$ of the list, the next $k$ integers are the vertices in the list.
### Output
- For each query, output two vertices so that their LCA is as close to the root as possible. If there are multiple valid solutions, any of them can be output.
### Constraints
- $1 \le n,q \le 10^5$.
- $2 \le k \le n$.
- $\sum{k} \le 2 \times 10^5$.
- $1 \le u_i \le n$.
### Example
Input:
```
8 7
1 2
2 3
1 4
2 5
4 6
5 7
7 8
5 4 5 2 2 6
3 2 2 3
6 6 2 5 3 2 2
3 4 3 3
5 6 3 8 7 2
4 2 1 8 5
2 5 2
```
Output:
```
2 6
2 3
2 6
3 4
2 6
1 8
2 5
```
