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\).

Định dạng đầu vào

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

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

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): \(N, Q \le 100\).
• Subtask 2 (20 điểm): \(N, Q \le 5000\).
• Subtask 3 (30 điểm): \(N, 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.