CF1578B.Building Forest Trails

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.

有 $n$ 个村庄均匀分布在一片浓密且不可穿越的森林中央的一个圆周上。自古以来，人们无法在村庄之间通行，但技术进步已带来巨大改变。如今，已有技术可在森林中修建可通行的小径。

修建过程包含 $m$ 个事件。每个事件要么是修建一条小径，要么是查询两个村庄在当前时刻是否连通。小径以连接两个村庄的直线段形式修建。一旦某条小径建成，任何人都可沿该小径从一个村庄步行至另一个村庄。

此外，若两条小径相交，则任何人可在交点处转向；若某人刚抵达一个村庄，而该村庄还有其他小径延伸出去，则这些小径也可用于继续通行。例如，若村庄按圆周顺序编号为 $1$ 至 $6$，且已修建小径 $1$–$3$、$2$–$4$ 和 $4$–$6$，则除第 $5$ 个村庄外，其余所有村庄均可从第 $1$ 个村庄到达。

给定 $m$ 个事件的列表，请对每个查询事件，判断此时所给定的两个村庄是否相互可达。

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.

第一行包含两个整数 $n$（$2 \le n \le 2\cdot 10^5$）和 $m$（$1 \le m \le 3\cdot 10^5$），分别表示村庄的数量和事件的数量。

接下来的 $m$ 行描述各个事件。每个事件由三个整数 $e$（$e$ 为 $1$ 或 $2$）、$v$（$1 \le v \le n$）和 $u$（$1 \le u \le n$，且 $u \ne v$）组成。若 $e = 1$，则该事件表示在村庄 $v$ 和 $u$ 之间修建一条小径；若 $e = 2$，则该事件为一次查询，询问村庄 $v$ 和 $u$ 是否连通。保证每条小径至多被修建一次。

村庄按顺时针顺序编号为 $1$ 至 $n$，围成一个圆圈。

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.

对于每个查询，如果村庄之间不可达，则输出字符 '0'；如果村庄之间可达，则输出 '1'。将所有查询的答案作为单个字符串，在一行中输出。