Cây là một khái niệm quan trọng trong lý thuyết đồ thị. Cây là một đồ thị mà trong đó 2 đỉnh bất kỳ đều được nối với nhau bằng đúng một đường đi. Cây là kiểu dữ liệu trừu tượng gồm một tập hợp hữu hạn các nút, giữa các nút có một quan hệ phân cấp gọi là quan hệ cha – con, trong đó có một nút r đặc biệt không có nút cha khác r gọi là gốc.

Với hai nút ~u, v~ bất kỳ của cây T, ~LCA(u, v)~ cho biết nút cha chung gần nhất của 2 nút ~u, v~. Tức là cho biết nút gần nhất là cha của cả ~u~ và ~v~ (không có nút nào là con của ~LCA(u, v)~ là cha của cả ~u~ và ~v~). Trong cây T, coi nút ~u~ là cha của ~u~ và ~u~ là con của ~u~.

Ví dụ cây dưới đây:

Nút 1 là gốc, 1 là cha của 2, 3, 4, 5; 2 là cha của 4, 5. Khi đó ~LCA(2, 3) = 1~; ~LCA(3, 4) = 1~; ~LCA(4, 5) = 2~;

Yêu cầu: Cho một cây T có ~n~ nút đánh số từ 1 đến ~n~ gồm ~n - 1~ cạnh nối giữa hai nút của cây. Tìm ~LCA(u, v)~ khi nút ~r~ là gốc.

Dữ liệu

Vào từ tệp văn bản LCA.INP

• Dòng đầu ghi số nguyên dương ~n~ là số nút của cây T;
• ~n - 1~ dòng tiếp mỗi dòng ghi 2 số nguyên dương ~u, v~ thể hiện một cạnh nối giữa 2 nút ~u, v~ trong cây T;
• Dòng tiếp theo là số nguyên dương ~q~ là số truy vấn;
• ~q~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương ~x, y, r~ (~1 \le x, y, r \le n~; ~n, q \le 10^5~)

Kết quả

Ghi ra tệp văn bản LCA.OUT gồm ~q~ dòng, mỗi dòng tương ứng là nút cha chung gần nhất của 2 nút ~x, y~ khi nút ~r~ làm gốc của cây.

Ví dụ

LCA.INP

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

LCA.OUT

1
5
2
5
3

Giới hạn

• Có 20% số test tương ứng với 20% số điểm của bài với ~n \le 10~; ~q \le 10~;
• Có 20% số test tương ứng với 20% số điểm của bài với ~10 < n \le 10^3~; ~q \le 10^3~;
• Có 60% số test tương ứng với 60% số điểm của bài với ~10^3 < n \le 10^5~; ~q \le 10^5~.