Cho một cây \(n\) đỉnh có gốc là \(1\). Có \(q\) truy vấn, mỗi truy vấn gồm một dãy \(k\) đỉnh: \(u_1,u_2,…,u_k\). Nhiệm vụ của bạn là chọn ra \(2\) đỉnh sao cho Tổ tiên chung gần nhất (LCA) của chúng là gần gốc nhất có thể.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(n,q\)
• \(n-1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v\) , có cạnh nối giữa \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn. Số nguyên đầu tiên là \(k\), kích cỡ của dãy đỉnh, \(k\) số nguyên tiếp theo là những đỉnh trong dãy.

Dữ liệu ra

• Với mỗi truy vấn, in ra hai đỉnh có LCA gần gốc nhất. Nếu có nhiều đáp án, in ra bất kì.

Ràng buộc

• \(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\)

Input 1

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 1

2 6
2 3
2 6
3 4
2 6
1 8
2 5