Building Forest Trails

题意翻译

在密林的中央，$n$ 个村庄坐落在一个巨大的圆上，将圆环顺次 $n$ 等分。自远古以来，从一个村庄旅行到另一个村庄是不可能完成的，任意两个村庄之间都互不连通。现在，我们有了新的技术，可以在密林当中开展工程，来让某些村庄之间联通。 工程包括 $m$ 个操作，分为建设一条道路和查询某两个村庄是否联通两类。一条道路是一条连接某两个村庄的线段，在道路被修建后，该条道路两端的村庄的人将可前往另端的村庄，即，这两个村庄将彼此联通。类似的，若村庄 $a$ 到 $b$ 联通，$b$ 到 $c$ 联通，那么 $a$ 到 $c$ 也将联通。 更进一步的，若两条道路在圆中交叉，那么任何人都将可以通过交叉所形成的岔路口。即，岔路口的两条路径两端的四个村庄也将彼此联通。我们给出一个例子：若村庄被沿顺时针顺序以 $1$ 到 $6$ 顺次标号，并且我们修建了 $1$ 到 $3$ ，$2$ 到 $4$ 和 $4$ 到 $6$ 的路径，那么除去 $5$ 号村庄之外的所有村庄都将联通。 给出 $m$ 个操作，你需要回答其中的全部询问。 $2 \le n \le 2·10^5,\ 1 \le m \le 3·10^5$ 输入共 $m+2$ 行。 - 第一行两个整数 $n,m$，意义如题面所示。 - 接下来的 $m$ 行， 每行三个整数 $e(e\in \{1,2\}),v(1\le v\le n),u(1\le u \le n)$。 - 若 $e=1$，即为修建一条 $v$ 到 $u$ 的道路。 - 若 $e=2$，查询 $v$ 到 $u$ 是否联通。 输出共一行。 输出一个字符串 $s$，其中 $s_i$ 代表第 $i$ 个查询操作的答案，下标从1开始。

题目描述

There are $ n $ villages lying equidistant on a circle in the middle of a thick, impassable forest. From ancient times, it was impossible to move from one village to another, but technical progress has changed a lot. Now, there is a technology to build passable trails in the forest. The building process consists of $ m $ events. Each event is either building a trail or querying if two villages are connected. Trails are built as straight lines connecting two villages. After a trail is built, anybody can walk along the trail from one village to another. Moreover, if two trails cross, anybody can turn at the intersection, and if other trails leave a village you have just reached, they can also be used to walk along. So, for example, if villages are numbered $ 1 $ to $ 6 $ in the order around the circle, and there are trails $ 1 $ to $ 3 $ , $ 2 $ to $ 4 $ , and $ 4 $ to $ 6 $ , then all villages, except the $ 5 $ -th, are reachable from the $ 1 $ -st village. Given a list of $ m $ events, for each query, find if two given villages are reachable from each other at that moment.

输入输出格式

输入格式

The first line contains two integers $ n $ ( $ 2 \le n \le 2\cdot 10^5 $ ) and $ m $ ( $ 1 \le m \le 3\cdot 10^5 $ ) — the number of villages and the number of events respectively. Next $ m $ lines contain events. Each event description consists of three integers $ e $ ( $ e $ is $ 1 $ or $ 2 $ ), $ v $ ( $ 1 \le v \le n $ ), and $ u $ ( $ 1 \le u \le n $ , $ u \ne v $ ). If $ e = 1 $ , then the event is building a trail between villages $ v $ and $ u $ . If $ e = 2 $ , then the event is a query if the villages $ v $ and $ u $ are connected. It is guaranteed that each trail is built at most once. Villages are numbered $ 1 $ to $ n $ in clockwise order around the circle.

输出格式

For each query print one character '0' if villages are not reachable, and '1' if villages are reachable from each other. Print answers for all queries as a single string in one line.

输入输出样例

输入样例 #1

6 9
1 1 3
1 4 6
2 3 4
1 2 4
2 1 2
2 1 3
2 1 4
2 6 1
2 5 3

输出样例 #1

011110

输入样例 #2

2 5
2 1 2
2 2 1
1 1 2
2 1 2
2 2 1

输出样例 #2

0011