G - Connectivity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

N 頂点からなる無向グラフがあり、 最初、どの 2 つの頂点も辺で結ばれていません。
Q 個のクエリが与えられるので与えられた順番に処理してください。
クエリは次の 2 種類のいずれかです。

  • 1 u v : 頂点 u と頂点 v を直接結ぶ辺が無いならばその間に無向辺を追加する。頂点 u と頂点 v を直接結ぶ辺があるならば、その辺を削除する。

  • 2 u v : 頂点 u から頂点 v へ辺を辿って移動することができるならば Yes を、そうでないならば No を出力する。

制約

  • 2 \leq N \leq 100
  • 1 \leq Q \leq 10000
  • 1 \leq u,v \leq N
  • u \neq v
  • 2 種類目のクエリが 1 回以上与えられる。
  • 入力は全て整数である。

入力

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

N Q
query_1
query_2
\vdots
query_Q

2 行目から Q+1 行目の各 query_i は次のいずれかの形で与えられる。

1 u v

2 u v

出力

2 種類目のクエリに対する答えを与えられた順に改行区切りで出力せよ。

入力例 1

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

出力例 1

Yes
No
  • 1 個目のクエリの直前の時点で、頂点 1 と頂点 2 は辺で結ばれていないため、辺を追加します。
  • 2 個目のクエリの直前の時点で、頂点 3 と頂点 2 は辺で結ばれていないため、辺を追加します。
  • 3 個目のクエリの時点で、1 , 2 個目のクエリで追加された辺を辿って、頂点 1 \to 頂点 2 \to 頂点 3 と移動できるため、Yes を出力します。
  • 4 個目のクエリの直前の時点で、頂点 2 と頂点 3 を直接結ぶ辺は存在するため、これを削除します。
  • 5 個目のクエリの時点では、頂点 1 と頂点 2 を結ぶ辺しか存在せず、頂点 1 から頂点 3 へは辿り着けないため、 No を出力します。

Score : 6 points

Problem Statement

There is an undirected graph with N vertices. Initially, no two vertices are connected by an edge.
Process the Q queries in the order they are given.
There are two kinds of queries shown below.

  • 1 u v: If there is no edge directly connecting Vertex u and Vertex v, add an undirected edge connecting them; if there is such an edge, delete it.

  • 1 u v: If it is possible to get from Vertex u to Vertex v by traversing edges, print Yes; otherwise, print No.

Constraints

  • 2 \leq N \leq 100
  • 1 \leq Q \leq 10000
  • 1 \leq u,v \leq N
  • u \neq v
  • There is at least one query of the second kind.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
query_1
query_2
\vdots
query_Q

Each query_i in the 2-nd through (Q+1)-th lines is in one of the following formats:

1 u v

2 u v

Output

Print the responses to the queries of the second kind, in the order they are given, separated by newlines.

Sample Input 1

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

Sample Output 1

Yes
No
  • Just before the 1-st query, Vertex 1 and Vertex 2 are not connected by an edge, so we add an edge.
  • Just before the 2-nd query, Vertex 3 and Vertex 2 are not connected by an edge, so we add an edge.
  • At the time of the 3-rd query, we can traverse the edges added in the 1-st and 2-nd queries to go Vertex 1 \to Vertex 2 \to Vertex 3, so we print Yes.
  • Just before the 4-th query, Vertex 3 and Vertex 2 are directly connected by an edge, so we delete it.
  • At the time of the 5-th query, only the edge connecting Vertex 1 and Vertex 2 exists, which does not enable us to get from Vertex 1 to Vertex 3, so we print No.