Permutation Construction on Rooted Tree

You are given a rooted tree with \(n\) vertices numbered \(1,2,\dots,n\) where vertex \(1\) is the root. For each vertex \(i\) (\(2 \le i \le n\)), its parent is given by \(f_i\). Also, you are given \(m\) pairs of integers \(a_1,b_1,\dots,a_m,b_m\). Your task is to construct a permutation \(p_1, p_2, \dots, p_m\) of the indices \(1,2,\dots,m\) such that the total cost does not exceed \(4\times10^9\).

The cost of a permutation \(p\) is defined as:

[ |S(a_{p_1})|+|S(b_{p_1})|+\sum_{i=2}^m \Bigl(|S(a_{p_{i-1}})\oplus S(a_{p_i})|+|S(b_{p_{i-1}})\oplus S(b_{p_i})|\Bigr), ]

where for any vertex \(x\), \(S(x)\) denotes the set of vertices in the subtree rooted at \(x\) (including \(x\) itself), \(|A|\) denotes the cardinality of set \(A\), and \(A\oplus B\) denotes the symmetric difference of sets \(A\) and \(B\) (i.e. the set of elements that appear in exactly one of \(A\) and \(B\)).

Your goal is to output any permutation \(p_1,p_2,\dots,p_m\) that meets the above cost constraint.

inputFormat

The input begins with an integer \(n\) on the first line.

The second line contains \(n-1\) space-separated integers \(f_2, f_3, \dots, f_n\) where \(f_i\) is the parent of vertex \(i\) (\(1\) is the root).

The next line contains an integer \(m\) which is the number of pairs.

Each of the following \(m\) lines contains two space-separated integers \(a_i\) and \(b_i\).

outputFormat

Output a permutation of the integers \(1,2,\dots,m\) (separated by spaces) representing an ordering of the given pairs such that the computed cost does not exceed \(4\times10^9\).

sample

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

1 2 3