G - ボールの転送ゲーム 解説 /

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

配点 : 366 点

問題文

高橋君は N 人の子供たちが参加するボールの転送ゲームを企画しています。

N 人の子供にはそれぞれ 1 から N までの番号が付けられています。子供 i は、ボールを受け取ると必ず子供 T_i にボールを渡します（ T_i \neq i ）。

ゲームは次のように進行します。

  1. まず、高橋君（子供たちとは別の人物）が子供 S にボールを渡します。子供 S はボールを受け取ります。
  2. 現在ボールを持っている子供 c は、ルールに従い子供 T_c にボールを渡そうとします。もし子供 T_c がこのゲーム中にまだ一度もボールを受け取ったことがなければ、子供 T_c はボールを受け取り、ステップ 2 を繰り返します。もし子供 T_c がこのゲーム中にすでにボールを受け取ったことのある子供であった場合（最初にボールを受け取った子供 S 自身である場合も含む）、ボールを渡さずにゲームは終了します。

Q 個のクエリが与えられます。各クエリでは、最初にボールを渡す子供の番号 S_j が指定されます。各クエリは独立であり、クエリごとに新たにゲームを最初から行います。それぞれのクエリについて、ゲーム中にボールを受け取った異なる子供の人数を求めてください。最初にボールを受け取った子供 S_j もこの人数に含みます。なお、高橋君は子供ではないため人数に含みません。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq N
  • 1 \leq T_i \leq N
  • T_i \neq i （ 1 \leq i \leq N ）
  • 1 \leq S_j \leq N （ 1 \leq j \leq Q ）
  • 同じ S_j の値が複数回与えられることもある。
  • 入力はすべて整数である。

入力

N Q
T_1 T_2 \ldots T_N
S_1
S_2
\vdots
S_Q
  • 1 行目には、子供の人数を表す N とクエリの数を表す Q が、スペース区切りで与えられる。
  • 2 行目には、子供 i がボールを渡す相手を表す T_i が N 個、スペース区切りで与えられる。
  • 続く Q 行では、各クエリで最初にボールを渡す子供の番号 S_j が 1 つずつ与えられる。

出力

Q 行出力せよ。 j 行目には、クエリ j のゲームにおいてボールを受け取った異なる子供の人数を出力せよ。

入力例 1

5 3
2 3 2 5 4
1
2
4

出力例 1

3
2
2

入力例 2

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

出力例 2

3
3
2
2
3

入力例 3

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

出力例 3

4
3
4
3
4
3
3
4

入力例 4

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

出力例 4

5
6
9
3
6
5
6
5
4
4
8
8
5
3
4
4
8
9
5
8

入力例 5

2 1
2 1
1

出力例 5

2

Score : 366 pts

Problem Statement

Takahashi is organizing a ball passing game in which N children participate.

Each of the N children is assigned a number from 1 to N. When child i receives the ball, they always pass it to child T_i (T_i \neq i).

The game proceeds as follows:

  1. First, Takahashi (who is a separate person from the children) passes the ball to child S. Child S receives the ball.
  2. The child c currently holding the ball attempts to pass the ball to child T_c according to the rules. If child T_c has never received the ball during this game, child T_c receives the ball, and step 2 is repeated. If child T_c has already received the ball during this game (including the case where T_c is child S who received the ball first), the ball is not passed and the game ends.

You are given Q queries. In each query, the number S_j of the child to whom the ball is initially passed is specified. Each query is independent, and a new game is played from the beginning for each query. For each query, find the number of distinct children who received the ball during the game. This count includes child S_j who received the ball first. Note that Takahashi is not a child and is therefore not included in the count.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq N
  • 1 \leq T_i \leq N
  • T_i \neq i (1 \leq i \leq N)
  • 1 \leq S_j \leq N (1 \leq j \leq Q)
  • The same value of S_j may be given multiple times.
  • All inputs are integers.

Input

N Q
T_1 T_2 \ldots T_N
S_1
S_2
\vdots
S_Q
  • The first line contains N, representing the number of children, and Q, representing the number of queries, separated by a space.
  • The second line contains N values T_i, separated by spaces, where T_i represents the child to whom child i passes the ball.
  • The following Q lines each contain one value S_j, the number of the child to whom the ball is initially passed in each query.

Output

Output Q lines. On the j-th line, output the number of distinct children who received the ball in the game for query j.

Sample Input 1

5 3
2 3 2 5 4
1
2
4

Sample Output 1

3
2
2

Sample Input 2

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

Sample Output 2

3
3
2
2
3

Sample Input 3

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

Sample Output 3

4
3
4
3
4
3
3
4

Sample Input 4

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

Sample Output 4

5
6
9
3
6
5
6
5
4
4
8
8
5
3
4
4
8
9
5
8

Sample Input 5

2 1
2 1
1

Sample Output 5

2