Một công ty có \(n\) nhân viên, tạo thành một cây phân cấp mà mỗi nhân viên đều có một sếp, trừ giám đốc (nhân viên số \(1\)).

Nhiệm vụ của bạn là xử lý \(q\) truy vấn dưới dạng: "Ai là sếp chung gần nhất của hai nhân viên \(a\) và \(b\) trong cây phân cấp?".

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số lượng nhân viên và số lượng truy vấn.
• Các nhân viên được đánh số từ \(1, 2, ..., n\), và nhân viên số \(1\) là giám đốc.
• Dòng tiếp theo chứa \(n - 1\) số nguyên \(e_2, e_3, ..., e_n\): với mỗi nhân viên từ \(2, 3, ..., n\), đó là sếp trực tiếp của họ.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi truy vấn chứa hai số nguyên \(a\) và \(b\): ai là sếp chung gần nhất của nhân viên \(a\) và \(b\)?

Dữ liệu ra:

• In ra kết quả cho mỗi truy vấn.

Ràng buộc

• \(1 \le n,q \le 2 \times 10^5\)
• \(1 \le e_i \le i\)
• \(1 \le a,b \le n\)

Input 1

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

Output 1

3
1
1