3124: The old man ring

$Xq$ of Rainbow Island has recently become obsessed with a game called Old Man Ring, in which there is a golden tree with $n$ nodes numbered $1-n$, and node 1 is the root node. Now $Xq$ and his roommate climb the golden tree in black. They start from the two nodes of the golden tree at the same time, at the same speed, moving one node at a time, and walking in opposite directions along the path between the two nodes.When they reach the same node or neighboring node, $Xq$ wants to know where they end up.There are a total of $q$ queries. Each query gives the node $x$ and $y$ where the two men are located. For each query, the last node number of the two men is output respectively.

The first line contains two integers , $n(1\leq n\leq 10^5)$ and $q(1\leq q\leq 10^5)$, representing the number of nodes in the tree and the total number of queries.

The next line contains $n-1$ numbers, with the $i$-th number representing the parent of node $i +1$.

The next $q$ lines, each containing two integers x and y, represent the initial location node of $Xq$ and his roommate.

Output the last node number of both persons for each query.

10 4
1 1 2 2 5 5 6 3 3
4 4
8 3
3 8
4 9

4 4
5 2
2 5
1 1