There is a forest $F$ of unrooted trees consisting of $N$ vertices. Initially, every tree in $F$ consists of a single vertex. Let's process the following queries:

• 1 A B: Add an edge connecting vertices $A$ and $B$. Before the query, there is no edge between $A$ and $B$.
• 2 A B: Remove an edge connecting vertices $A$ and $B$. Before the query, there is an edge between $A$ and $B$.
• 3 A B: Check whether there is a path from vertex $A$ to vertex $B$. If there is, output $1$; otherwise output $0$.

All $A$ and $B$ satisfy $1 \le A, B \le N$, $A \ne B$, and all edges are undirected.

Input

The first line contains the number of vertices $N$ ($2 \le N \le 100{,}000$) and the number of queries $M$ ($1 \le M \le 100{,}000$). From the second line onward, $M$ lines each contain one query. Only inputs where the result of each query is a forest are given.

Output

Print the results of type 3 queries, one per line.

Examples

Input 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

Output 1

0
1
0
1