Bài toán

Một công ty có ~ n ~ nhân viên, được tổ chức theo dạng cây phân cấp, trong đó mỗi nhân viên (trừ giám đốc chung) đều có một người quản lý. Bạn cần trả lời ~ q ~ truy vấn dưới dạng: ai là cấp trên chung thấp nhất (LCA - Lowest Common Ancestor) của hai nhân viên ~ a ~ và ~ b ~?

Đầu vào

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ q ~: số nhân viên và số truy vấn (~ 1 \leq n, q \leq 2 \cdot 10^5 ~).
• Tiếp theo là ~ n-1 ~ số nguyên ~ e_2, e_3, \ldots, e_n ~: ~ e_i ~ là người quản lý trực tiếp của nhân viên ~ i ~.
• Cuối cùng là ~ q ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~: cần tìm cấp trên chung thấp nhất của ~ a ~ và ~ b ~.

Đầu ra

• In ra ~ q ~ số nguyên, mỗi số là kết quả của một truy vấn.

Kiểm tra với ví dụ

Input:

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

Output:

3
1
1

Giải thích:

• LCA của ~ 4 ~ và ~ 5 ~ là ~ 3 ~.
• LCA của ~ 2 ~ và ~ 4 ~ là ~ 1 ~.
• LCA của ~ 1 ~ và ~ 3 ~ là ~ 1 ~.