Problem B
Disjoint Sets

Maintain a family of disjoint sets, initially the singletons $ \{ 0\} ,\{ 1\} , \ldots ,\{ n-1\} $, under the following operations:

0 (“query”)

The query operation takes two elements $s$ and $t$ and determines if $s$ and $t$ belong to the same set. More precisely, if $s\in S$ and $t\in T$ then print “1” if $S=T$ and print “0” if $S\neq T$.

1 (“union”)

The union operation takes two elements $s$ and $t$ and creates the union of the two sets containing $s$ and $t$. More precisely, if $s\in S$ and $t\in T$ with $S\neq T$ then $S$ and $T$ are removed from the family and replaced by the set $S\cup T$. (If $S=T$ then nothing happens.)

2 (“move”)

(Test groups 2 and 4 only.) The move operation takes two elements $s$ and $t$ and moves the element $s$ into the set containing the element $t$. More precisely, if $s\in S$ and $t\in T$ with $S\neq T$ then $S$ is changed to $S-\{ s\} $ and $T$ is changed to $T\cup \{ s\} $. (If $S=T$ then nothing happens.)

Note that these operations maintain invariantly that the sets in the family are disjoint.

Test groups

There are 4 different test groups.

Any solution to test group 3 also solves test group 1. Any solution to test group 4 solves all the other test groups.

Input

The input starts with two positive integers $n$, $m$, on the first line. The integer $n$ is the initial number of singletons. The following $m$ lines are of the form “0 $s$ $t$” or “1 $s$ $t$” or “2 $s$ $t$”, representing query, union, and move. In test groups 1 and 3, move never occurs. You can assume $0\leq s< n$, $0\leq t< n$ and $m\geq 1$.

Output

For each query, write a single line containing 1 or 0 as described above.

4 9
0 0 1
1 0 1
0 0 1
1 1 2
0 1 2
0 0 3
1 2 3
0 2 3
0 0 3

0
1
1
0
1
1

4 9
0 0 1
1 0 1
0 0 1
1 1 2
0 1 2
0 0 3
2 2 3
0 0 1
0 1 2

0
1
1
0
1
0

2 2
1 0 0
0 0 1

0