Processing math: 100%
Shallow - MarisaOJ: Marisa Online Judge

Shallow

Time limit: 1000 ms
Memory limit: 256 MB

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: u1,u2,…,uk. 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≤n,q≤105.
  • 2≤k≤n.
  • ∑k≤2×105.
  • 1≤ui≤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