#109. 并查集

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

这是一道模板题。

维护一个 nn 点的无向图,支持:

  • 加入一条连接 uuvv 的无向边
  • 查询 uuvv 的连通性

由于本题数据较大,因此输出的时候采用特殊的输出方式:用 0011 代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数 mod 998244353\text{mod} ~ 998244353 的值。

请务必使用快读。

输入格式

第一行包含两个整数 n,mn,m,表示点的个数和操作的数目。

接下来 mm 行每行包括三个整数 op,u,v\text{op},u,v

  • 如果 op=0\text{op} = 0,则表示加入一条连接 uuvv 的无向边;
  • 如果 op=1\text{op} = 1,则表示查询 uuvv 的连通性。

输出格式

一行包括一个整数表示答案。

样例

样例输入

3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1

样例输出

5

样例解释

答案串为 101101

数据范围与提示

n4000000,m8000000n\le 4000000,m\le 8000000

By zyz