Problem Description

Given a rooted tree with $n$ vertices, the vertices are numbered $1,\dots,n$, where $1$ is the root. $f_2,\dots,f_n$ denote the parents of vertices $2,\dots,n$, respectively.

Given $m$ pairs of integers $a_1,b_1,\dots,a_m,b_m$, you need to construct a permutation $p_1,\dots,p_m$ of $1,\dots,m$ such that the cost of this permutation does not exceed $4\times 10^9$.

The cost of a permutation is defined as:

$|S(a_{p_1})|+|S(b_{p_1})|+\sum\limits_{i=2}^m |S(a_{p_{i-1}})\oplus S(a_{p_i})|+|S(b_{p_{i-1}})\oplus S(b_{p_i})|$

Here, $S(x)$ is the set of vertices in the subtree rooted at $x$, $|A|$ is the number of elements in set $A$, and $A\oplus B$ is the symmetric difference of sets $A$ and $B$ (that is, the set of elements that appear in exactly one of $A$ and $B$).

Input Format

The first line contains two integers $n,m$.

The second line contains $n-1$ integers $f_2,\dots,f_n$.

The next $m$ lines each contain two integers representing $a_i,b_i$, for $i=1,\dots,m$.

Output Format

Output $m$ lines, each with one integer, representing $p_1,\dots,p_m$ in order.

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

2
3
1

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

For $25\%$ of the testdata, $n,m\le 10^4$.

For $50\%$ of the testdata, $n,m\le 2\times 10^5$.

For $75\%$ of the testdata, $n,m\le 5\times 10^5$.

For $100\%$ of the testdata, $1\le n,m\le 10^6$, $1\le f_i\le i-1$, $1\le a_i,b_i\le n$.

Constraints.

Translated by ChatGPT 5