题目描述

维护一个 $\red {n}$ 点的无向图，支持：

• 加入一条连接 $\red {u}$ 和 $\red {v}$ 的无向边
• 查询 $\red {u}$ 和 $\red {v}$ 的连通性

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

输入格式

第一行包含两个整数 $\red {n, m}$ ，表示点的个数和操作的数目。

接下来 $\red {m}$ 行每行包括三个整数 $\red {op, u, v}$。

• 如果 $\red {op = 0}$，则表示加入一条连接 $\red {u}$ 和 $\red {v}$ 的无向边；
• 如果 $\red {op = 1}$，则表示查询 $\red {u}$ 和 $\red {v}$ 的连通性。

输出格式

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

样例

输入样例

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

输出样例

5

数据范围与提示

$\red{2 \le n \le 10^6, 1 \le m \le 3 \times 10^6, 1 \le u, v \le n}$