(talca.*)

Trong một cây có gốc, tổ tiên chung của hai nút \(u,\ v\) là nút thấp nhất làm tổ tiên chung của hai nút \(u,\ v\); ký hiệu là \(lca(u,v)\).

Bạn được cho một cây gồm \(n\) nút. Hãy trả lời \(q\) truy vấn dạng \(r,\ u,\ v\); nghĩa là hãy tìm \(LCA(u,v)\) với gốc cây là nút \(r\)

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\) (\(1 \leq n \leq 10^{5})\) cho biết số nút trên cây.

+ \(n - 1\) dòng tiếp theo mỗi dòng ghi hai số \(x,\ y\ (1 \leq x,\ y \leq n)\) cho biết một cạnh trên cây.

+ Dòng tiếp theo ghi số nguyên \(q\ (1 \leq q \leq 10^{5})\) cho biết số lượng truy vấn.

+ \(q\) dòng tiếp theo, mỗi dòng ghi 3 số \(r,\ u,\ v\) cho biết một truy vấn.

Kết quả:

+ Gồm \(q\) dòng, mỗi dòng trả lời cho một truy vấn tưng ứng trong Input.

Ví dụ:

Input	Output
4 1 2 2 3 1 4 2 1 4 2 2 4 2	1 2

Solution: