📘 Mô tả

Cho một cây gồm n đỉnh được đánh số từ 1 đến n. Cây không định hướng và không có chu trình. Bạn sẽ nhận được q truy vấn. Mỗi truy vấn gồm ba số nguyên r, u, v, yêu cầu bạn tìm tổ tiên chung gần nhất của u và v trong cây khi gốc là đỉnh r.

📥 Input

• Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 10⁵): số đỉnh của cây.
• n - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y: thể hiện cạnh nối giữa đỉnh x và y.
• Dòng tiếp theo chứa số nguyên q (1 ≤ q ≤ 10⁵): số lượng truy vấn.
• q dòng tiếp theo, mỗi dòng chứa ba số nguyên r, u, v: truy vấn tìm tổ tiên chung gần nhất của u và v trong cây khi gốc là r.

📤 Output

In ra q dòng, mỗi dòng là một số nguyên — tổ tiên chung gần nhất của u và v trong cây khi gốc là r.

🧪 Ví dụ

Input:

5
1 2
1 3
2 4
2 5
3
1 4 5
2 4 3
4 5 3

Output:

2
2
2