给您一个无向图,其中 $$$n$$$ 顶点编号从 $$$1$$$ 到 $$$n$$$。最初没有边缘。
系统会要求您对图表执行一些查询。令 $$$last$$$ 为第二类型最新查询的答案,在第一个此类查询之前将其设置为 $$$0$$$。那么查询如下:
- $$$1~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — 在顶点 $$$(x + last - 1)~mod~n + 1$$$ 和 $$$(y + last - 1)~mod~n + 1$$$ 之间添加一条无向边(如果尚不存在),否则将其删除;
- $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — 检查顶点 $$$(x + last - 1)~mod~n + 1$$$ 和 $$$(y + last - 1)~mod~n + 1$$$ 之间是否存在路径,该路径仅通过当前存在的路径边,如果是,则将 $$$last$$$ 设置为 $$$1$$$,否则将 $$$0$$$ 设置为 $$$0$$$。
祝你好运!
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — 分别是顶点数和查询数。
以下 $$$m$$$ 行中的每一行都包含上述两种类型之一的查询。保证至少有一个第二类型的查询。
输出
打印一个由字符“0”和“1”组成的字符串。第 $$$i$$$ 个字符应该是第二个类型的第 $$$i$$$ 个查询的答案。因此字符串的长度应该等于第二类型查询的数量。
示例
输入 #1
5 9 1 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1 2 4 2 3 4 1 1 3 2 4 3
输出 #1
1010
输入 #2
3 9 1 1 2 1 2 3 1 3 1 2 1 3 1 3 2 2 2 3 1 1 2 2 1 2 2 1 2
输出 #2
1101
注意
第一个示例中转换后的查询是:
- 1 1 2
- 1 1 3
- 2 3 2
- 1 3 5
- 2 4 5
- 1 2 4
- 2 3 4
- 1 2 4
- 2 5 4
第二个示例中转换后的查询为:
- 1 1 2
- 1 2 3
- 1 3 1
- 2 1 3
- 1 1 3
- 2 3 1
- 1 2 3
- 2 2 3
- 2 1 2