Cho một cấu trúc cây phả hệ gồm \(N\) thành viên, trong đó người đứng đầu dòng họ là thành viên 1. Có Q truy vấn, mỗi truy vấn yêu cầu tìm tổ tiên chung gần nhất (LCA) của hai thành viên u và \(v\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và Q (\(2 \le N, Q \le 200000\)). - N-\(1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (\(1 \le u, v \le N\)) thể hiện một quan hệ trực tiếp trên cây.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên u và \(v\) mô tả truy vấn tìm LCA.

Kết quả ra

• Với mỗi truy vấn, in ra chỉ số của tổ tiên chung gần nhất trên một dòng mới.

Ví dụ

Input

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

Output

2
1
1

Ràng buộc & Subtasks