题目描述

给定一个$n$个点的无向图，支持以下两种操作：

1. 加入一条从 $u$到$v$的无向边
2. 查询$u$和$v$的连通性

由于本题目的数据量比较大，所以我们输出的时候采用较为特殊的输出方式：用$0$或$1$代表我们每一个询问的答案，将每一个询问的答案依次从左到右排列得到的串视为一个二进制数，输出将这个二进制数$mod 998244353$的值

输入格式

第一行包含两个整数$n$和$m$，代表点的个数和操作的数目

接下来$m$行，每行包括三个整数$op, u, v$

1. 如果$op == 0$，则代表加入一条连接$u$和$v$的无向边
2. 如果$op == 1$，则代表查询$u$和$v$的连通性

输出格式

一个整数代表答案

样例

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

5

提示

数据范围

$n \le 4 * 10^{6}$

$m \le 8 * 10^{6}$