Forced Online Queries Problem
Contest: Educational Codeforces Round 72 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, divide and conquer, dsu, graphs, trees

You are given an undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Initially there are no edges.

You are asked to perform some queries on the graph. Let $$$last$$$ be the answer to the latest query of the second type, it is set to $$$0$$$ before the first such query. Then the queries are the following:

- $$$1~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — add an undirected edge between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$ if it doesn't exist yet, otherwise remove it;
- $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$) — check if there exists a path between the vertices $$$(x + last - 1)~mod~n + 1$$$ and $$$(y + last - 1)~mod~n + 1$$$, which goes only through currently existing edges, and set $$$last$$$ to $$$1$$$ if so and $$$0$$$ otherwise.

Good luck!

Input format:
The first line contains two integer numbers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of queries, respectively.

Each of the following $$$m$$$ lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.

Output format:
Print a string, consisting of characters '0' and '1'. The $$$i$$$-th character should be the answer to the $$$i$$$-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
The converted queries in the first example are:

- 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

The converted queries in the second example are:

- 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

Example input:
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

Example output:
1010

Example input:
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

Example output:
1101

Editorial:
The problem directly tells you do solve some kind of Dynamic Connectivity Problem.
You could use the online approach with Link-Cut Tree if you'd had its implementation beforehand. There is also a nice modification to the $$$log^2$$$ solution of the offline version of DCP (check out the comment).
I'd tell the solution which is probably the easiest to come up with and to code.
Let's recall the sqrt-optimization method of solving DCP. Process blocks of queries of size $$$P$$$ one at a time. Split the edges into two groups:
1. The edges which were added on queries before the block and aren't touched by the queries in the block;
2. the edges modified by the queries in the block.
The first type of edges can be added to the graph before the block processing starts. You can use DSU for that. The second type contains no more than $$$P$$$ edges. Maintain the list of those of them which exist in the graph. On each ask query add them to graph, then delete them. This can be done explicitly by doing DFS only over these edges and the vertices which correspond to the connected components on the edges of the first type. Implicitly doing DSU merges for these edges and rolling them back is a viable option as well (costs extra log factor but has lower constant).
It's easy to see that it isn't hard to modify this solution to our problem. Let's define the edges of the first type more generally: the edges which were added on queries before the block and could not be touched by the queries in the block. So neither $$$(v, u)$$$ from the add query, nor $$$(v~mod~n + 1, u~mod~n + 1)$$$ could be of the first type. Now there might be $$$2P$$$ edges of the second type in the list. However, that doesn't make the complexity any worse.
Process block the same way, rebuild the DSU with the edges of the first type every $$$P$$$ queries.
The overall complexity can be $$$O((n + m) \sqrt{m})$$$ if you use DFS or $$$O((n + m) \sqrt{m \log n})$$$ if you use DSU (notice how the rebuild is $$$P \cdot O(n + m)$$$ and the query is $$$m \cdot O(\frac{m}{P} \cdot \log n)$$$ and set the size of the block so that these parts are about the same).