P - 偶数けんけん Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題

辺が 1 つもない頂点数 N の無向グラフ G があります。 Q 個のクエリが与えられるので順に処理してください。

クエリは以下の 2​ 種類のどちらかです。

  • 1 u v : 頂点 u と頂点 v の間に辺を張る。
  • 2 u v : 頂点 u から頂点 v への偶数長のウォークが存在するかを判定し、出力する。
ウォークとは？ グラフ G の頂点 s, t に対して、頂点の列 (v_1,v_2,\ldots,v_k) であって v_1 = s, v_k = t かつ任意の 1\le i\le k-1 について v_i, v_{i+1} が辺で結ばれているものを頂点 s から t へのウォークと呼びます。またこのとき、 ウォークの長さは k-1 です。 同じ頂点を複数回通ってよいことに注意してください。

制約

  • 2\le N \le 2\times 10^5
  • 1\le Q \le 2\times 10^5
  • 任意のクエリにおいて、 1\le u \lt v \le N
  • 1 種類目のクエリにおいて、同じ (u, v) は 2 回以上現れない
  • 入力はすべて整数

入力

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリは次の 2 種類の形式のどちらかです。

1 u v

2 u v

出力

2 種類目のクエリについて、偶数長のウォークが存在するときは Yes を、存在しないときは No をそれぞれ 1 行ずつ出力してください。

入力例 1

4 8
2 1 4
1 1 2
2 1 4
1 2 4
2 1 4
2 2 4
1 1 4
2 2 4

出力例 1

No
No
Yes
No
Yes

1 種類目のクエリによってグラフは図1〜図4のように変化します。始め、グラフは図1の状態です。

  • 1 番目のクエリ：頂点 1 と頂点 4 の間には長さが偶数のウォークが存在しないので No を出力します。
  • 2 番目のクエリ：頂点 1 と頂点 2 の間に辺が追加され、グラフは図2の状態になります。
  • 3 番目のクエリ：頂点 1 と頂点 4 の間には長さが偶数のウォークが存在しないので No を出力します。
  • 4 番目のクエリ：頂点 2 と頂点 4 の間に辺が追加され、グラフは図3の状態になります。
  • 5 番目のクエリ：頂点 1 と頂点 4 の間には長さ 2 のウォークが存在するので Yes を出力します。
  • 6 番目のクエリ：頂点 2 と頂点 4 の間には奇数長のウォークしか存在しないため、No を出力します。
  • 7 番目のクエリ：頂点 1 と頂点 4 の間に辺が追加され、グラフは図4の状態になります。
  • 8 番目のクエリ：頂点 2 と頂点 4 の間には長さ 2 のウォークが存在するので Yes を出力します。

入力例 2

10 20
1 1 3
1 1 4
2 5 8
2 3 4
1 3 7
2 3 7
2 1 7
1 5 9
2 5 7
2 4 7
1 5 8
2 8 9
2 6 10
1 1 8
2 1 5
2 4 8
2 3 5
1 3 9
2 3 8
2 3 7

出力例 2

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