Cho một cây \(N\) đỉnh có gốc là \(1\). Có \(Q\) truy vấn tìm LCA (tổ tiên chung gần nhất) của hai đỉnh \(x\) và \(y\).

Input

• Dòng đầu tiên là số nguyên dương \(N\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một cạnh của cây.
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một cặp số \((x, y)\).

Output

• Với mỗi truy vấn, in ra kết quả cần tìm trên từng dòng.

Constraints

• \(1 \le N, Q \le 10^5\)
• \(1 \le x, y \le N\)

Example

7
6 1
6 4
4 7
3 4
1 2
2 5
6
3 3
7 7
1 3
5 7
7 6
2 4

3
7
1
1
6
1

Nguồn: CD DHBB 2020