Forced Online Queries Problem
题意翻译
### 题目描述
给你一个有$n$个点的无向图,点的编号从$1$到$n$,最初图中没有边
给定两种操作:
- $1\ x\ y(1\le n,x\neq y)$如果在点$(x+lstans-1)mod\ n+1$与边$(y+lstans-1)mod\ n+1$之间有边,则删,无边则加
- $2\ x\ y(1\le x,y \le n,x\neq y)$检查点$(x+lstans-1)mod\ n+1$与点$(y+lstans-1)mod\ n+1$之间的连通性,联通则输出1,否则输出0
(这里定义$lastans$为上一次操作$2$的结果,特别的,在第一次操作$2$之前,$lastans=0$)
### 输入格式
第一行输入两个整数$n,m(2\le n,m\le 2\cdot 10^5)$,$n$代表点的个数,而$m$代表操作的个数
接下来有$m$行,具体格式如题目描述中所写(保证有至少一次操作$2$)
### 输出格式
对于每一个操作$2$,输出一个整数,为这个询问的答案(不用空格隔开)
### 说明/提示
对于样例$1$,输入所代表的实际询问如下:
- 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
对于样例$2$,输入所代表的实际询问如下:
- 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
题目描述
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.
输入输出样例
输入样例 #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
说明
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