Bình đang nghiên cứu gia phả của một dòng họ lớn. Gia phả có cấu trúc cây với \(N\) thành viên, đánh số từ 1 đến \(N\), trong đó thành viên 1 là thủy tổ. Mỗi thành viên (trừ thủy tổ) có đúng một người cha trực tiếp.

Bình cần trả lời \(Q\) câu hỏi: "Tổ tiên chung gần nhất của hai thành viên u và v là ai?" Nói cách khác, hãy tìm thành viên ở vị trí sâu nhất trong gia phả mà là tổ tiên của cả u và \(v\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và Q (\(1 \le N, Q \le 10^5\)). - N-\(1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)).

Kết quả ra

• Với mỗi truy vấn, in ra số hiệu của tổ tiên chung gần nhất.

Ví dụ

Input

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

Output

2
1
1
1

Ràng buộc

• Subtask 1 (20 điểm): \(Q \le 100\).
• Subtask 2 (20 điểm): \(Q \le 5000\).
• Subtask 3 (30 điểm): \(Q \le 10^{5}, cây có dạng đường thẳng\).
• Subtask 4 (30 điểm): Không có ràng buộc gì thêm.