A12955 | Forced Online Queries Problem

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!

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.

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.