5674: 【模板题】并查集 I
[Creator : ]
Description
维护一个 $n$ 点的无向图,支持下面两个操作:
如果 $\text{op}=0$,则表示加入一条连接 $u,\ v$ 的无向边;
如果 $\text{op}=1$,则表示查询 $u,\ v$ 的连通性。
由于本题数据较大,因此输出的时候采用特殊的输出方式:用 $0$ 或 $1$ 代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数 $\bmod 998244353$ 的值。
如果 $\text{op}=0$,则表示加入一条连接 $u,\ v$ 的无向边;
如果 $\text{op}=1$,则表示查询 $u,\ v$ 的连通性。
由于本题数据较大,因此输出的时候采用特殊的输出方式:用 $0$ 或 $1$ 代表每个询问的答案,将每个询问的答案依次从左到右排列,把得到的串视为一个二进制数,输出这个二进制数 $\bmod 998244353$ 的值。
Input
第一行包含两个整数 $n,\ m\ (n \leq 4,000,000,\ m \leq 8,000,000)$,表示点的个数和操作的数目。
接下来 $m$ 行每行包括三个整数 $op,\ u,\ v$ 。
接下来 $m$ 行每行包括三个整数 $op,\ u,\ v$ 。
Output
一行包括一个整数表示答案。
Sample 1 Input
3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1
Sample 1 Output
5