Bessie and Jonell's Meeting Point

Bessie and Jonell are great friends. However, since Farmer John scrambles where the cows graze every day, they sometimes can be quite far from each other and are unable to talk. The farm's pastures form a tree structure: each pasture (except the root pasture #1) has exactly one parent, and there exists a unique path between any two pastures.

Every day, Bessie and Jonell will meet at the closest pasture that is an ancestor of both their locations. In other words, they will meet at the lowest common ancestor (LCA) of the two pastures where they are grazing.

The input consists of a map of the farm and a schedule for several days. Your task is to compute the meeting place for each day.

Note: Any formulas mentioned are given in \( \LaTeX \) format. For example, the meeting point is defined as the lowest common ancestor (LCA) of nodes \( u \) and \( v \) in the tree.

inputFormat

The input begins with two integers \( N \) and \( M \) (\(1 \leq N, M \leq 1000\)). \( N \) is the number of pastures, and \( M \) is the number of days.

The next line contains \( N-1 \) space-separated integers. The \( i\)-th integer (for \( i = 2,3,\dots,N \)) represents \( P_i \), the parent of pasture \( i \). Pasture 1 is the root and has no parent.

Each of the following \( M \) lines contains two integers \( B_k \) and \( J_k \) (\(1 \leq B_k, J_k \leq N\)), indicating Bessie’s and Jonell’s pastures on day \( k \), respectively.

outputFormat

For each day, output the meeting pasture (i.e. the lowest common ancestor of \( B_k \) and \( J_k \)) on a new line.

sample

9 6
1 1 1 2 8 1 8 6
2 7
4 2
1 1
4 1
7 5
9 5

1
2
1
1
8
6