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