← 返回题目列表

Codeforces · 1217/F

F. 强制在线查询问题

中文机器翻译题面 查看原题

给您一个无向图,其中 $$$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