暂无测试数据。

Description

维护一个 \(n\) 点的无向图，支持：

• 加入一条连接 \(u\) 和 \(v\) 的无向边
• 查询 \(u\) 和 \(v\) 的连通性

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

请务必使用快读。

Format

Input

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

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

• 如果 \(\text{op}=0\)，则表示加入一条连接 \(u\) 和 \(v\) 的无向边；
• 如果 \(\text{op}=1\)，则表示查询 \(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

Output

5

Explanation

答案串为 \(0101\)。

Limitation

Data

\(n\le 4000000,m\le 8000000\)

Time and Space

2s, 125MB.

Source

loj #109

update by Shuchong