题目描述

这是一道模板题。
维护一个 nnn 点的无向图，支持：
加入一条连接 uuu 和 vvv 的无向边
查询 uuu 和 vvv 的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用 000 或 111 代表每个询问的答案，将每个询问的答案一次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数 mod 998244353\text{mod} ~ 998244353mod 998244353 的值。

输入格式

第一行包含两个整数 n,mn,mn,m，表示点的个数和操作的数目。
接下来 mmm 行每行包括三个整数 op,u,v\text{op},u,vop,u,v。
如果 op=0\text{op} = 0op=0，则表示加入一条连接 uuu 和 vvv 的无向边；
如果 op=1\text{op} = 1op=1，则表示查询 uuu 和 vvv 的连通性。

输出格式

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

样例

样例输入

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

样例输出

5

样例解释

答案串为 101101101。

数据范围与提示

n≤4000000,m≤8000000n\le 4000000,m\le 8000000n≤4000000,m≤8000000

注意

此题评测速度可能较慢，因为数据包过大