E - Tag Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君と青木君が、N 個の部屋からなる建物の中で鬼ごっこをしています。部屋には 1 から N までの番号が付けられており、部屋間は M 本の一方通行の廊下で結ばれています。i 番目の廊下は部屋 U_i から部屋 V_i への一方向にのみ通行できます。同じ部屋から同じ部屋への廊下（自己ループ）は存在せず、同じ始点・終点の組を持つ廊下が複数存在することもありません。

高橋君が逃げる側、青木君が鬼（追いかける側）です。二人はともにグラフの構造を完全に知っており、互いの現在位置を常に把握しています。

ゲーム開始時、高橋君は部屋 S に、青木君は部屋 R にいます（S \neq R）。ゲーム開始時点では二人は異なる部屋にいるため捕獲は起こらず、直ちに最初のターンが始まります。各ターンは以下のステップ 1〜4 からなります。捕獲が発生しない限り、ターンは無限に繰り返されます。

  1. 高橋君の行動： 高橋君は、今いる部屋を始点とする廊下を 1 本選んでその先の部屋へ移動するか、現在の部屋にとどまるかを選びます。（今いる部屋を始点とする廊下が 1 本もない場合は、とどまることしかできません。）
  2. 捕獲判定： この時点で高橋君と青木君が同じ部屋にいれば、高橋君は捕まり、ゲーム終了です。
  3. 青木君の行動： 捕まっていなければ、青木君は、今いる部屋を始点とする廊下を 1 本選んでその先の部屋へ移動するか、現在の部屋にとどまるかを選びます。（今いる部屋を始点とする廊下が 1 本もない場合は、とどまることしかできません。）
  4. 捕獲判定： この時点で高橋君と青木君が同じ部屋にいれば、高橋君は捕まり、ゲーム終了です。

ステップ 2 およびステップ 4 のいずれでも捕まらなければ、次のターンのステップ 1 に進みます。

両者が最適に行動するとき、結果は次の二つのうちちょうど一方になります：

  • 捕まる： 高橋君がどのような戦略を取っても、青木君は有限ターン以内に必ず高橋君を捕まえることができる。
  • 逃げ切れる： 高橋君が適切な戦略を取れば、青木君がどのように行動しても永遠に捕まらずにいられる。

Q 個のクエリが与えられます。j 番目のクエリでは、高橋君の初期位置 S_j と青木君の初期位置 R_j が与えられるので、両者が最適に行動したとき高橋君が逃げ切れるかどうかを判定してください。各クエリは互いに独立です。

制約

  • 2 \leq N \leq 500
  • 0 \leq M \leq N(N-1)
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i（自己ループはない）
  • (U_i, V_i) の組はすべて異なる（多重辺はない）
  • 1 \leq Q \leq 100000
  • 1 \leq S_j \leq N
  • 1 \leq R_j \leq N
  • S_j \neq R_j
  • (S_j, R_j) の組が複数のクエリで重複することもある
  • 入力はすべて整数

入力

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
Q
S_1 R_1
S_2 R_2
\vdots
S_Q R_Q
  • 1 行目には、部屋の数を表す整数 N と、廊下の数を表す整数 M が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目では、i 番目の廊下の始点 U_i と終点 V_i がスペース区切りで与えられる。
  • 次の行にはクエリ数 Q が与えられる。
  • 続く Q 行のうち j 行目では、j 番目のクエリにおける高橋君の初期位置 S_j と青木君の初期位置 R_j がスペース区切りで与えられる。

出力

Q 行出力してください。j 行目には、j 番目のクエリに対して、両者が最適に行動したとき高橋君が永遠に逃げ切れるなら YES を、高橋君が必ず有限ターン以内に捕まるなら NO を出力してください。

入力例 1

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

出力例 1

YES
YES
NO
YES
YES

入力例 2

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

出力例 2

YES
NO
NO
YES
NO
NO

入力例 3

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

出力例 3

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

入力例 4

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

出力例 4

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

入力例 5

2 0
4
1 2
2 1
1 2
2 1

出力例 5

YES
YES
YES
YES

Score : 433 pts

Problem Statement

Takahashi and Aoki are playing tag in a building consisting of N rooms. The rooms are numbered from 1 to N, and they are connected by M one-way corridors. The i-th corridor allows passage only in one direction, from room U_i to room V_i. There are no corridors from a room to itself (no self-loops), and there are no multiple corridors with the same start and end points.

Takahashi is the runner (evader), and Aoki is the chaser (it). Both players have complete knowledge of the graph structure and always know each other's current position.

At the start of the game, Takahashi is in room S and Aoki is in room R (S \neq R). Since the two players are in different rooms at the start, no capture occurs, and the first turn begins immediately. Each turn consists of the following steps 1–4. Turns repeat indefinitely unless a capture occurs.

  1. Takahashi's action: Takahashi chooses one corridor starting from his current room and moves to the room at its end, or he chooses to stay in his current room. (If there are no corridors starting from his current room, he can only stay.)
  2. Capture check: If Takahashi and Aoki are in the same room at this point, Takahashi is captured and the game ends.
  3. Aoki's action: If Takahashi has not been captured, Aoki chooses one corridor starting from his current room and moves to the room at its end, or he chooses to stay in his current room. (If there are no corridors starting from his current room, he can only stay.)
  4. Capture check: If Takahashi and Aoki are in the same room at this point, Takahashi is captured and the game ends.

If Takahashi is not captured in either step 2 or step 4, the game proceeds to step 1 of the next turn.

When both players act optimally, the result is exactly one of the following two outcomes:

  • Captured: No matter what strategy Takahashi uses, Aoki can always capture Takahashi within a finite number of turns.
  • Escapes: If Takahashi uses an appropriate strategy, he can avoid being captured forever regardless of how Aoki acts.

You are given Q queries. In the j-th query, you are given Takahashi's initial position S_j and Aoki's initial position R_j. Determine whether Takahashi can escape forever when both players act optimally. Each query is independent.

Constraints

  • 2 \leq N \leq 500
  • 0 \leq M \leq N(N-1)
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i (no self-loops)
  • All pairs (U_i, V_i) are distinct (no multiple edges)
  • 1 \leq Q \leq 100000
  • 1 \leq S_j \leq N
  • 1 \leq R_j \leq N
  • S_j \neq R_j
  • The pair (S_j, R_j) may appear in multiple queries
  • All inputs are integers

Input

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
Q
S_1 R_1
S_2 R_2
\vdots
S_Q R_Q
  • The first line contains an integer N representing the number of rooms and an integer M representing the number of corridors, separated by a space.
  • The following M lines each contain the start U_i and end V_i of the i-th corridor, separated by a space.
  • The next line contains the number of queries Q.
  • The following Q lines each contain Takahashi's initial position S_j and Aoki's initial position R_j for the j-th query, separated by a space.

Output

Output Q lines. On the j-th line, output YES if Takahashi can escape forever when both players act optimally, or NO if Takahashi will always be captured within a finite number of turns.

Sample Input 1

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

Sample Output 1

YES
YES
NO
YES
YES

Sample Input 2

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

Sample Output 2

YES
NO
NO
YES
NO
NO

Sample Input 3

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

Sample Output 3

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

Sample Input 4

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

Sample Output 4

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

Sample Input 5

2 0
4
1 2
2 1
1 2
2 1

Sample Output 5

YES
YES
YES
YES