有 $N$ 个顶点组成的无根树森林 $F$。初始时，$F$ 中的所有树都只由一个顶点构成。请执行以下查询：

• 1 A B：添加一条连接顶点 $A$ 和 $B$ 的边。查询给出前，$A$ 和 $B$ 之间没有边。
• 2 A B：删除一条连接顶点 $A$ 和 $B$ 的边。查询给出前，$A$ 和 $B$ 之间有边。
• 3 A B：检查是否存在从 $A$ 到 $B$ 的路径。如果存在，输出 $1$；否则输出 $0$。

所有 $A$ 和 $B$ 满足 $1 \le A, B \le N$，$A \ne B$，且所有边均为无向边。

输入格式

第一行包含顶点个数 $N$（$2 \le N \le 100{,}000$）和查询个数 $M$（$1 \le M \le 100{,}000$）。接下来 $M$ 行，每行给出一个查询。输入保证每次查询操作后森林仍然是森林。

输出格式

对于每个 3 号查询，输出一行结果。

样例

输入样例 1

5 11
3 1 5
1 1 2
1 1 3
1 3 4
1 5 4
3 1 5
2 4 5
3 1 5
2 3 4
1 3 5
3 1 5

输出样例 1

0
1
0
1