Cho một cây \(n\) đỉnh, có đỉnh gốc là \(1\).

Cho \(q\) truy vấn có dạng \((u,v)\), tìm tổ tiên chung gần nhất của \(u\) và \(v\)

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\)
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) thể hiện có cạnh nối \(u\) và \(v\)
• \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\)

Dữ liệu ra

• In ra \(q\) dòng, mỗi dòng ứng với một đáp án của câu truy vấn

Điều kiện

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

Input 1

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

Output 1

2
1
1