D - Reachability Query 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 頂点 M 辺の有向グラフが与えられます。
頂点には 1 から N の番号がついており、i 番目の辺は頂点 X_i から頂点 Y_i への有向辺です。
最初全ての頂点は白色です。

Q 個のクエリが与えられるので順に処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 v：頂点 v を黒色にする
  • 2 v：頂点 v から辺を辿って黒色の頂点に到達可能かどうか判定する

制約

  • 1\leq N \leq 3\times 10^5
  • 0\leq M \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 1\leq X_i,Y_i \leq N
  • 自己辺をもたない。すなわち X_i \neq Y_i
  • 多重辺をもたない。すなわち (X_i,Y_i) は相異なる
  • クエリにおいて 1 \leq v \leq N
  • 入力は全て整数

入力

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

N M
X_1 Y_1
\vdots
X_M Y_M
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i は i 番目のクエリを表し、以下のいずれかの形式で与えられる。

1 v

2 v

出力

2 種類目のクエリの個数を q として q 行出力せよ。

i 行目には、i 番目の 2 種類目のクエリにおいて到達可能なら Yes、到達不可能なら No と出力せよ。

入力例 1

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

出力例 1

Yes
No
Yes
  • 最初、与えられたグラフは下図一番左の通りです。
  • 1 番目のクエリにより頂点 3 が黒色になり、下図中央のようになります。
  • 2 番目のクエリにおいて、頂点 1 から黒色の頂点 3 に到達可能です。
  • 3 番目のクエリにおいて、頂点 4 から黒色の頂点に到達することはできません。
  • 4 番目のクエリにより頂点 5 が黒色になり、下図右のようになります。
  • 5 番目のクエリにおいて、頂点 4 から黒色の頂点 5 に到達可能です。

図

Score : 425 points

Problem Statement

You are given a directed graph with N vertices and M edges.
The vertices are numbered from 1 to N, and the i-th edge is a directed edge from vertex X_i to vertex Y_i.
Initially, all vertices are white.

Process Q queries in order. Each query is of one of the following two types:

  • 1 v: Color vertex v black.
  • 2 v: Determine whether it is possible to reach a black vertex by following edges from vertex v.

Constraints

  • 1\leq N \leq 3\times 10^5
  • 0\leq M \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 1\leq X_i,Y_i \leq N
  • There are no self-loops, that is, X_i \neq Y_i.
  • There are no multiple edges, that is, (X_i,Y_i) are distinct.
  • In queries, 1 \leq v \leq N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 Y_1
\vdots
X_M Y_M
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i represents the i-th query and is given in one of the following formats:

1 v

2 v

Output

Let q be the number of queries of the second type. Output q lines.

The i-th line should contain Yes if a black vertex is reachable in the i-th query of the second type, and No otherwise.

Sample Input 1

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

Sample Output 1

Yes
No
Yes
  • Initially, the given graph is as shown in the leftmost figure below.
  • By the first query, vertex 3 becomes black, as shown in the center figure.
  • In the second query, it is possible to reach black vertex 3 from vertex 1.
  • In the third query, it is not possible to reach a black vertex from vertex 4.
  • By the fourth query, vertex 5 becomes black, as shown in the rightmost figure.
  • In the fifth query, it is possible to reach black vertex 5 from vertex 4.

Figure