Description
. 
On the left is Katsura, and on the right is Kagura.
Katsura has decided that the group has become far too chaotic. Kagura keeps causing trouble, people keep sending messages to the wrong person, and nobody seems to know who should handle what.
So Katsura creates a new rule called Controlled Centralize.
There are \(n\) members in the group, numbered from \(1\) to \(n\). Member \(1\) is the top leader. Every other member has exactly one direct supervisor.
Under this rule, when two members need to communicate, argue, report an incident, or complain about Kagura eating the emergency snacks again, they are not allowed to deal with it directly. The matter must be passed upward through the chain of command.
The person who handles it is the lowest supervisor who oversees both of them.
You are given the hierarchy of the group. For each communication request, determine who will end up handling the situation.
Hints
For testcases 5-8, you might want to refer to this link's Chapter 18 Tree Queries section for optimization.
Constraints
- \(1 \le n, q \le 2 \times 10^5\)
- \(1 \le a, b \le n\)
Input
Line 1: two integers \(n\), the number of members, and \(q\), the number of requests.
Line 2: \(n - 1\) integers. For each member \(2\) to \(n\), the given integer is their direct supervisor's number.
Each of the next \(q\) lines contains two integers \(a\) and \(b\), meaning members \(a\) and \(b\) need to communicate.
Output
For each request, print the member number who will handle the communication under the Controlled Centralized rule.