Tý có một hệ thống phân cấp gia phả gồm \(N\) thành viên, được đánh số từ 1 đến N (thành viên 1 là tổ tiên gốc). Các mối quan hệ cha-con được biểu diễn bởi \(N-1\) mối liên kết. Với Q truy vấn, mỗi truy vấn cho hai thành viên u và v, hãy tìm tổ tiên chung gần nhất (gần với u và \(v\) nhất) của hai người đó trong gia phả.

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

• Dòng đầu chứa hai số nguyên dương \(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ố \(u, v\) mô tả mối quan hệ cha-con (không xác định thứ tự).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) cần tìm tổ tiên chung.

Định dạng đầu ra

• Với mỗi truy vấn, in ra tổ tiên chung gần nhất của \(u\) và \(v\) trên một dòng.

Ví dụ

Input:

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

Output:

1
2
1
1

Ràng buộc