Migrated from Lutece 2948 星星与薰衣草

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

温馨提示:注意整型的表示范围和四则运算取模的性质

“Lyn...你知道它们有个神奇的秘密吗？尽管这满天的星星全都这么闪闪发光...但其中有许多都在很久以前就已经消失了。”

“消失了？”

“是啊......即便是星星也没法永远存在。”

“但那样的话......为什么我们还能看见它们呢？”

“这个是因为啊，当它们还存在的时候，放出的光芒就非常明亮......明亮到足以穿过无比漫长的时空，所以直到现在还能到达我们身边。”

“哇哦......那样的话，我觉得我应该要感谢它们，没有了它们，我就看不见这片薰衣草地了。”

“我想，那或许你也得感谢这些薰衣草了。因为要是没有它们，这里也就没东西可看了，对吧？”

“对！虽然薰衣草不长在天上，可是......这样我才更喜欢。我可以在它们身边玩耍，闻到它们的香气，还能看到它们就在眼前的样子！星星们都在很远很远的地方，但是......我猜它们也都有自己的事情要做。不管是薰衣草还是星星，我都一点也不想改变它们！”

“噢？一点也不想改变啊。那要是你能成为其中之一的话，你更愿意当哪一边呢？”

“嗯...好吧，我还是更喜欢薰衣草，所以呢...所以我...我想成为一颗星星！”

“为什么是星星呢，你不是更喜欢薰衣草吗？”

“哎呀，爸爸...当然是，为了让每个人都能看到这些薰衣草啦！我会把最最耀眼的光芒洒在这片田野上，让这里亮得像白天一样，那样的话，每个人都能随时看到薰衣草是多美好的东西啦！”

“看来你会成为一颗了不起的星星呢，Lyn......”

---

夜空中有 $n$ 颗星星，编号为 $0,1,...,n-1$ , 起初所有星星都是孤立的。 依次执行 $m$ 个操作。你可以在一些星星之间连线，形成星座（星星之间的连线是无向边，星座是由星星组成的连通块），也需要快速判断两颗星星是否已经在同一星座之中。

Input

第一行两个整数 $n,m$ , 表示星星的个数和操作的数目。 接下来的 $m$ 行，每行包含三个整数 $op, x, y$。

• 如果 $op = 0$ , 则在编号为 $x$ 和 $y$ 的星星之间连线。
• 如果 $op = 1$ , 则询问编号为 $x$ 和 $y$ 的星星是否位于同一星座中。如果是，答案为1，否则答案为0。

保证至少有一个 $op=1$ 的操作。

Output

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

Samples

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

5

Constraints

$1 \le n \le 2 \times 10^6, 0 \le m \le 4 \times 10^6$

Note

三个询问的答案依次为 $1,0,1$,构成的串为 $101$, 它的值为 $5$, 输出 $5 ~ \text{mod} ~ 998244353$ 的值 $5$。 建议使用较为高效的输入输出方式。

Resources

2023 UESTC ICPC Training for Data Structures