E - 最も深い共通の上司 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君の会社では、社員の管理体制が木構造の組織図で表されています。

社員は 1 から N までの番号で表されます。社員 1 は社長であり、組織図の最上位（根）に位置します。

各社員 i（ 2 \le i \le N ）には直属の上司がちょうど 1 人いて、その番号は P_i です。

この情報により、社員 1 を根とする N 頂点の根付き木が定まります。

社員 a から直属の上司をたどることを 0 回以上繰り返して社員 b に到達できるとき、社員 b を社員 a の 上司 と呼びます。

特に、各社員は自分自身の上司でもあります。また、社員 1 は全社員の上司です。

根付き木において、ある頂点の 深さ とは、根からその頂点までのパスに含まれる辺の数のことをいいます。根（社員 1）の深さは 0 です。

Q 個の問い合わせが与えられます。

k 番目の問い合わせでは社員の番号 X_k と Y_k が与えられるので、社員 X_k と社員 Y_k の両方の上司である社員のうち、深さが最も大きい社員の番号を求めてください。このような社員はちょうど 1 人存在することが証明できます。

なお、社員 X_k が社員 Y_k の上司である場合は答えは X_k であり、社員 Y_k が社員 X_k の上司である場合は答えは Y_k です（ X_k = Y_k の場合を含みます）。

制約

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq P_i < i （ 2 \leq i \leq N ）
  • 1 \leq X_k, Y_k \leq N （ 1 \leq k \leq Q ）
  • 入力はすべて整数である

入力

N Q
P_2 P_3 \ldots P_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
  • 1 行目には、社員数を表す整数 N と、問い合わせ数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、N-1 個の整数 P_2, P_3, \ldots, P_N がスペース区切りで与えられる。P_i は社員 i の直属の上司の番号を表す。
  • 3 行目から Q+2 行目まで、各問い合わせが与えられる。
  • 2 + k 行目には、 k 番目の問い合わせとして、整数 X_k と Y_k がスペース区切りで与えられる。

出力

Q 行出力せよ。

k 行目には、 k 番目の問い合わせに対する答えを整数で出力せよ。

入力例 1

7 5
1 1 2 2 3 3
4 5
4 6
6 7
2 7
3 3

出力例 1

2
1
3
1
3

入力例 2

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

出力例 2

1
1
5
1
1

入力例 3

15 8
1 1 2 2 3 3 4 4 5 6 6 7 10 10
8 9
8 14
11 12
14 15
13 15
10 14
2 12
6 13

出力例 3

4
2
6
10
1
10
1
3

入力例 4

25 14
1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 11 13 14 16 18 21
20 12
20 25
22 23
24 19
17 23
14 15
21 6
18 24
1 25
11 12
5 6
8 16
17 18
2 25

出力例 4

5
2
3
10
1
7
6
18
1
5
2
8
4
2

入力例 5

2 4
1
1 1
1 2
2 2
2 1

出力例 5

1
1
2
1

Score : 466 pts

Problem Statement

In Takahashi's company, the management structure of employees is represented by an organizational chart in the form of a tree structure.

Employees are numbered from 1 to N. Employee 1 is the president and is positioned at the top (root) of the organizational chart.

Each employee i (2 \le i \le N) has exactly one direct superior, whose number is P_i.

This information defines a rooted tree with N vertices, rooted at employee 1.

If employee b can be reached from employee a by following direct superiors zero or more times, then employee b is called a superior of employee a.

In particular, each employee is also a superior of themselves. Additionally, employee 1 is a superior of all employees.

In a rooted tree, the depth of a vertex is the number of edges on the path from the root to that vertex. The depth of the root (employee 1) is 0.

You are given Q queries.

In the k-th query, employee numbers X_k and Y_k are given. Find the employee number of the employee who is a superior of both employee X_k and employee Y_k and has the greatest depth. It can be proven that exactly one such employee exists.

Note that if employee X_k is a superior of employee Y_k, the answer is X_k, and if employee Y_k is a superior of employee X_k, the answer is Y_k (including the case where X_k = Y_k).

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq P_i < i (2 \leq i \leq N)
  • 1 \leq X_k, Y_k \leq N (1 \leq k \leq Q)
  • All input values are integers

Input

N Q
P_2 P_3 \ldots P_N
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
  • The first line contains an integer N representing the number of employees and an integer Q representing the number of queries, separated by a space.
  • The second line contains N-1 integers P_2, P_3, \ldots, P_N separated by spaces. P_i represents the employee number of the direct superior of employee i.
  • From the 3rd line to the (Q+2)-th line, each query is given.
  • The (2 + k)-th line contains integers X_k and Y_k separated by a space, representing the k-th query.

Output

Print Q lines.

On the k-th line, print the answer to the k-th query as an integer.

Sample Input 1

7 5
1 1 2 2 3 3
4 5
4 6
6 7
2 7
3 3

Sample Output 1

2
1
3
1
3

Sample Input 2

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

Sample Output 2

1
1
5
1
1

Sample Input 3

15 8
1 1 2 2 3 3 4 4 5 6 6 7 10 10
8 9
8 14
11 12
14 15
13 15
10 14
2 12
6 13

Sample Output 3

4
2
6
10
1
10
1
3

Sample Input 4

25 14
1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 11 13 14 16 18 21
20 12
20 25
22 23
24 19
17 23
14 15
21 6
18 24
1 25
11 12
5 6
8 16
17 18
2 25

Sample Output 4

5
2
3
10
1
7
6
18
1
5
2
8
4
2

Sample Input 5

2 4
1
1 1
1 2
2 2
2 1

Sample Output 5

1
1
2
1