在一片无法通行的茂密森林中央,有 $$$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