E - Reachability Query Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 頂点 0 辺の無向グラフが与えられます。
頂点には 1,2,\dots,N の番号が付けられており、最初は全ての頂点が白色です。
以下の 3 種類のクエリを合計 Q 個処理して下さい。

  • タイプ 1 : 頂点 u,v を結ぶ無向辺を追加する。
  • タイプ 2 : 頂点 v が白色なら黒色に、黒色なら白色に変更する。
  • タイプ 3 : 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるか判定し、到達できるなら Yes 、到達できないなら No と答える。

制約

  • 入力は全て整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le Q \le 6 \times 10^5
  • タイプ 1 のクエリは以下の制約を満たす。
    • 1 \le u < v \le N
    • 各クエリについて、そのクエリより前に u,v を結ぶ辺は追加されていない。
  • タイプ 2,3 のクエリは以下の制約を満たす。
    • 1 \le v \le N

入力

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

但し、 \rm{Query}_i は i 個目のクエリを表す。

タイプ 1 のクエリは以下の形式で与えられる。

1 u v

タイプ 2 のクエリは以下の形式で与えられる。

2 v

タイプ 3 のクエリは以下の形式で与えられる。

3 v

出力

タイプ 3 のクエリが現れる度に、その解答を次の通りに出力せよ。

  • 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるなら Yes
  • 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できないなら No

入力例 1

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

出力例 1

No
Yes
No
Yes
Yes
No

この入力では、グラフは最初 5 頂点 0 辺です。
この入力には 12 個のクエリが含まれます。

  • 1 個目のクエリは 3 2 です。
    • この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
  • 2 個目のクエリは 2 2 です。
    • 頂点 2 は白色なので、黒色に変更します。
  • 3 個目のクエリは 3 2 です。
    • この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
  • 4 個目のクエリは 1 2 5 です。
    • 頂点 2,5 を結ぶ辺を追加します。
  • 5 個目のクエリは 1 3 4 です。
    • 頂点 3,4 を結ぶ辺を追加します。
  • 6 個目のクエリは 3 4 です。
    • この時点で頂点 4 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
  • 7 個目のクエリは 3 5 です。
    • この時点で頂点 5 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
  • 8 個目のクエリは 1 4 5 です。
    • 頂点 4,5 を結ぶ辺を追加します。
  • 9 個目のクエリは 1 1 3 です。
    • 頂点 1,3 を結ぶ辺を追加します。
  • 10 個目のクエリは 3 1 です。
    • この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
  • 11 個目のクエリは 2 2 です。
    • 頂点 2 は黒色なので、白色に変更します。
  • 12 個目のクエリは 3 1 です。
    • この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。

Score : 450 points

Problem Statement

You are given an undirected graph with N vertices and zero edges.
The vertices are numbered 1,2,\dots,N, and initially all vertices are white.
Process a total of Q queries of the following three types:

  • Type 1 : Add an undirected edge connecting vertices u and v.
  • Type 2 : If vertex v is white, change it to black; if it is black, change it to white.
  • Type 3 : Determine whether a black vertex can be reached from vertex v by traversing zero or more edges; report Yes if reachable, and No otherwise.

Constraints

  • All input values are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le Q \le 6 \times 10^5
  • Type 1 queries satisfy the following constraints:
    • 1 \le u < v \le N
    • For each query, no edge connecting u and v has been added before that query.
  • Type 2,3 queries satisfy the following constraints:
    • 1 \le v \le N

Input

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

where \rm{Query}_i represents the i-th query.

Type 1 queries are given in the following format:

1 u v

Type 2 queries are given in the following format:

2 v

Type 3 queries are given in the following format:

3 v

Output

For each type 3 query, output the answer as follows:

  • Yes if a black vertex can be reached from vertex v by traversing zero or more edges;
  • No if no black vertex can be reached from vertex v by traversing zero or more edges.

Sample Input 1

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

Sample Output 1

No
Yes
No
Yes
Yes
No

In this input, the graph initially has five vertices and zero edges.
This input contains 12 queries.

  • The 1st query is 3 2.
    • At this point, no black vertex can be reached from vertex 2 by traversing zero or more edges, so report No.
  • The 2nd query is 2 2.
    • Vertex 2 is white, so change it to black.
  • The 3rd query is 3 2.
    • At this point, black vertex 2 can be reached from vertex 2 by traversing zero or more edges. Therefore, report Yes.
  • The 4th query is 1 2 5.
    • Add an edge connecting vertices 2,5.
  • The 5th query is 1 3 4.
    • Add an edge connecting vertices 3,4.
  • The 6th query is 3 4.
    • At this point, no black vertex can be reached from vertex 4 by traversing zero or more edges, so report No.
  • The 7th query is 3 5.
    • At this point, black vertex 2 can be reached from vertex 5 by traversing zero or more edges. Therefore, report Yes.
  • The 8th query is 1 4 5.
    • Add an edge connecting vertices 4,5.
  • The 9th query is 1 1 3.
    • Add an edge connecting vertices 1,3.
  • The 10th query is 3 1.
    • At this point, black vertex 2 can be reached from vertex 1 by traversing zero or more edges. Therefore, report Yes.
  • The 11th query is 2 2.
    • Vertex 2 is black, so change it to white.
  • The 12th query is 3 1.
    • At this point, no black vertex can be reached from vertex 1 by traversing zero or more edges, so report No.