K - 巨大企業 解説 /

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

注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

ある企業には N 人の社員、社員 1, \ldots, N が在籍する。このうち一人は社長であり、上司を持たない。その他の社員はみなちょうど一人の直属の上司を持つ。あなたのデータベースによると、社員 i (1 \leqq i \leqq N) の直属の上司は社員 p_i である (ただし社員 i が社長である場合は p_i = -1 となっている)。この上下関係に循環は存在しない。

このデータを用いて、二つの社員番号 a, b を入力すると社員 a が社員 b の部下であるかを判定するサービスを作りたい。ここで、社員 a が社員 b の部下であるとは、社員 a から直属の上司を辿っていくことで社員 b に到達できることを意味する。

サービスに入力される Q 個の社員番号の組 (a_1, b_1), \ldots, (a_Q, b_Q) が与えられる。これらのそれぞれに対して Yes または No を出力するプログラムを作成せよ。

制約

  • 2 \leqq N \leqq 150,000
  • 各 i = 1, \ldots, N に対し、p_i = -1 または 1 \leq p_i \leq N
  • p_i = -1 なる i はちょうど 1 つ存在する。
  • 社員間の上下関係に循環は存在しない。
  • 1 \leqq Q \leqq 100,000
  • 1 \leqq a_i, b_i \leqq N
  • a_i \neq b_i

入力

入力は以下の形式で標準入力から与えられる。

N
p_1
p_2
:
p_N
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

出力

Q 行出力せよ。i 行目 (1 \leqq i \leqq Q) は、社員 a_i が社員 b_i の部下であれば Yes、そうでなければ No とすること。

入力例 1

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

出力例 1

Yes
Yes
No
Yes
Yes
No

社員 1 (社長) の直属の部下が社員 2, 3、社員 2 の直属の部下が社員 4,5、社員 3 の直属の部下が社員 6,7 である。

例えば、1 個目の組 (7, 1) に対しては、社員 1 は社員 7 の直属の上司 (社員 3) の直属の上司であるため Yes と出力する。

入力例 2

20
4
11
12
-1
1
13
13
4
6
20
1
1
20
10
8
8
20
10
18
1
20
18 14
11 3
2 13
13 11
10 15
9 5
17 11
18 10
1 16
9 4
19 6
5 10
17 8
15 8
5 16
6 20
3 19
10 12
5 13
18 1

出力例 2

No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
Yes

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

A certain company has N members, Member 1, \ldots, N. One of them is the president and has no boss. Each of the other members has exactly one immediate boss. According to your database, the immediate boss of Member i (1 \leq i \leq N) is Member p_i (p_i = -1 if Member i is the president). There is no cyclic relationship among those members.

Based on this database, you want to create a web service that, when two numbers a and b representing two members are given, determines whether Member a is junior to Member b. Here, Member a is said to be junior to Member b if and only if Member b can be reached from Member a by tracing the relationship between the members in upward direction only.

Given are Q pairs of numbers (a_1, b_1), \ldots, (a_Q, b_Q), each representing two members. Write a program that prints Yes or No for each of them.

Constraints

  • 2 \leq N \leq 150000
  • For each i = 1, \ldots, N, p_i = -1 or 1 \leq p_i \leq N.
  • There exists a unique i such that p_i = -1.
  • There is no cyclic relationship among the members.
  • 1 \leq Q \leq 100000
  • 1 \leq a_i, b_i \leq N
  • a_i \neq b_i

Input

Input is given from Standard Input in the following format:

N
p_1
p_2
:
p_N
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain Yes if Member a_i is junior to Member b_i, and No otherwise.

Sample Input 1

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

Sample Output 1

Yes
Yes
No
Yes
Yes
No

The immediate juniors of Member 1 (the president) are Member 2, 3, the immediate juniors of Member 2 are Member 4, 5, and the immediate juniors of Member 3 are Member 6, 7.

For example, for the first pair (7, 1), Member 1 is the immediate boss of "the immediate boss of Member 7" (Member 3), so we print Yes.

Sample Input 2

20
4
11
12
-1
1
13
13
4
6
20
1
1
20
10
8
8
20
10
18
1
20
18 14
11 3
2 13
13 11
10 15
9 5
17 11
18 10
1 16
9 4
19 6
5 10
17 8
15 8
5 16
6 20
3 19
10 12
5 13
18 1

Sample Output 2

No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes
No
No
No
Yes