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