Cho một cây gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm tổ tiên chung gần nhất của ~u~ và ~v~.

Tổ tiên chung gần nhất của ~u~ và ~v~ là đỉnh sâu nhất đồng thời là tổ tiên của cả ~u~ và ~v~ (mỗi đỉnh được coi là tổ tiên của chính nó).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

7 3
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 6
2 7

Đầu ra:

2
1
1

Giải thích: Đỉnh ~4~ và ~5~ đều là con của ~2~ nên tổ tiên chung gần nhất là ~2~. Với ~(4, 6)~ và ~(2, 7)~, hai đỉnh nằm ở hai nhánh khác nhau của gốc nên đáp án là ~1~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~

Có thể ~u = v~, khi đó đáp án chính là ~u~. Cây có thể sâu tới ~10^5~ nên hãy tránh đệ quy khi duyệt cây.