P1015 【模板】并查集

P1015 【模板】并查集

Description

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

  • 加入一条连接 uuvv 的无向边
  • 查询 uuvv 的连通性 由于本题数据较大,因此输出的时候采用特殊的输出方式:用 0011 代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数 mod  998244353\mod 998244353 的值。

请务必使用快读。

Format

Input

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

接下来 mm 行每行包括三个整数 op,u,vop, u, v

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

Output

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

Sample

Input

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

Output

Note

答案为 01010101

Limitation

n4×106,m8×106n \le 4 \times 10 ^ 6, m \le 8 \times 10 ^ 6

信息

难度
9
分类
(无)
标签
递交数
13
已通过
3
通过率
23%
上传者