📘 Mô tả

Cho một cây gồm n đỉnh được đánh số từ 1 đến n. Gốc của cây là đỉnh số 1. Bạn sẽ nhận được q truy vấn, mỗi truy vấn gồm hai đỉnh u và v, yêu cầu bạn tìm tổ tiên chung gần nhất (LCA) của hai đỉnh này trong cây.

📥 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à đỉnh 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 hai số nguyên u và v: truy vấn tìm tổ tiên chung gần nhất của u và v.

📤 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.

🧪 Ví dụ

Input:

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

Output:

2
1
1

📎 Ghi chú

• Truy vấn 1: LCA(4, 5) = 2.
• Truy vấn 2: LCA(4, 3) = 1.
• Truy vấn 3: LCA(2, 3) = 1.