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\le n,q\le 2\cdot {10}^5$).
• Tiếp theo là $n-1$ số nguyên $e_2,e_3,\dots ,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$.