LCA

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

Input

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

Dữ liệu đảm bảo \(1 \le N, Q \le 10^5\) và \(1 \le x, y \le N\).

Output

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

Sample Input 1

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

Sample Output 1

3
7
1
1
6
1