Tổ Tiên Chung Gần Nhất

Cho một cây có gốc gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Đỉnh $1$ là gốc. Với mỗi đỉnh $v$ từ $2$ đến $n$, input cho biết cha trực tiếp $p_v$ của $v$; luôn có $1\le p_v<v$. Vì vậy, các quan hệ cha tạo thành đúng một cây.

Một đỉnh $x$ được gọi là tổ tiên của $v$ nếu $x=v$ hoặc có thể đi từ $v$ lên cha trực tiếp một số lần để tới $x$. Với hai đỉnh $a,b$, tổ tiên chung gần nhất của chúng là tổ tiên chung có độ sâu lớn nhất, tức đỉnh chung đầu tiên gặp được khi lần lượt đi từ $a$ và $b$ về gốc.

Hãy trả lời $q$ truy vấn, mỗi truy vấn yêu cầu tìm tổ tiên chung gần nhất của hai đỉnh đã cho.

Input

• Dòng đầu chứa hai số nguyên $n,q$.
• Dòng thứ hai chứa $n-1$ số nguyên $p_2,p_3,\dots ,p_n$, trong đó $p_v$ là cha trực tiếp của đỉnh $v$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a,b$ mô tả một truy vấn.
• Khi $n=1$, dòng thứ hai không chứa số nào và có thể được bỏ qua.

Output

• Với mỗi truy vấn, in trên một dòng chỉ số của tổ tiên chung gần nhất của hai đỉnh tương ứng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le p_v<v$ với mọi $2\le v\le n$.
• $1\le a,b\le n$.
• Các giới hạn áp dụng cho một test duy nhất; input không có nhiều test case.

Scoring

• Subtask $1$ ($50$ điểm): $n,q\le 2000$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

8 5
1 1 2 2 3 6 6
4 5
4 7
7 8
3 8
1 5

2
1
6
3
1