← 返回题目列表

AtCoder · practice2_a

A. 不相交集并集

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

分数: 100 点

问题陈述

给你一个无向图 N 顶点和 0 边缘。工艺流程 Q 以下类型的查询。

  • 0 u v:添加边缘 (u, v).
  • 1 u v:打印 1 if u 和 v 位于同一连接组件中, 0 否则。

约束

  • 1 \leq N \leq 200,000
  • 1 \leq Q \leq 200,000
  • 0 \leq u_i, v_i \lt N

输入

输入由标准输入按以下格式给出:

N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q

出力

对于后一种类型的每个查询,打印答案。


示例输入 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

示例输出 1

0
1
0
1