← 返回题目列表

AtCoder · tessoku_book_bn

A66. 连接查询

中文机器翻译题面 查看原题

配点: 1000 点

問題文

頂点数 N 的图,以下 更快地处理 2 类型的查询。 添加一条在两个方向上连接

  • 查询 1:頂点 u 与边缘 v 的边。
  • 查询 2:頂点 u 与边缘 v 回答它们是否属于同一个连接组件。

然而,最初图中没有边,给出的查询数为 Q 块。

制約

  • 2 \leq N \leq 100000
  • 1 \leq Q \leq 100000
  • \operatorname{Query}_i\ (1\leq i\leq Q) 就是全部 它是 t_i u_i v_i 格式 请注意,
  • t_i \in \{1,2\}\ (1\leq i\leq Q)
  • 1 \leq u_i \lt v_i \leq N\ (1\leq i\leq Q)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

\operatorname{Query}_i 是 您也可以写 i 表示查询的信息。 查询 它以 1 输出 1 u v,查询 它以 2 输出 2 u v 格式给出。 详细信息请参见输入示例。

出力

查询 2 的答案。


入力例 1

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

出力例 1

No
Yes

查询 1 ,图表发生如下变化:


入力例 2

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

出力例 2

No
No
Yes
Yes
No