← 返回题目列表

Codeforces · 1578/B

B. 建设森林步道

中文机器翻译题面 查看原题

在一片无法通行的茂密森林中央,有 $$$n$$$ 个村庄等距分布在一个圆圈上。从古代开始,从一个村庄搬到另一个村庄是不可能的,但技术进步已经改变了很多。现在,有一种技术可以在森林中建造可通行的小径。

构建过程由 $$$m$$$ 事件组成。每个事件要么构建一条路径,要么查询两个村庄是否相连。小径呈直线连接两个村庄。一条小路建成后,任何人都可以沿着小路从一个村庄走到另一个村庄。

此外,如果两条小路交叉,任何人都可以在路口转弯,如果其他小路离开你刚刚到达的村庄,也可以用来沿着它们走。因此,举例来说,如果村庄按圆周围的顺序编号为 $$$1$$$ 到 $$$6$$$,并且有路径 $$$1$$$ 到 $$$3$$$、$$$2$$$ 到 $$$4$$$、$$$4$$$ 到 $$$6$$$,那么除了第 $$$5$$$ 之外的所有村庄都可以从$$$1$$$-st 村庄。

给定 $$$m$$$ 事件列表,对于每个查询,查找两个给定村庄在该时刻是否可以相互到达。

输入

第一行包含两个整数 $$$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$$$。

输出

对于每个查询,如果无法到达村庄,则打印一个字符“0”;如果村庄之间可以相互到达,则打印“1”。将所有查询的答案打印为一行中的单个字符串。

示例

输入 #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