$N$ sommets formant une forêt d'arbres non enracinés $F$. Initialement, chaque arbre de $F$ est constitué d'un seul sommet. Effectuons les requêtes suivantes :

• 1 A B : ajoute une arête reliant les sommets $A$ et $B$. Avant la requête, il n'y a pas d'arête entre $A$ et $B$.
• 2 A B : supprime l'arête reliant les sommets $A$ et $B$. Avant la requête, il y a une arête entre $A$ et $B$.
• 3 A B : vérifie s'il existe un chemin de $A$ à $B$. Si oui, affiche $1$ ; sinon, affiche $0$.

Tous les $A$ et $B$ vérifient $1 \le A, B \le N$, $A \ne B$, et toutes les arêtes sont non orientées.

Entrée

La première ligne contient le nombre de sommets $N$ ($2 \le N \le 100\,000$) et le nombre de requêtes $M$ ($1 \le M \le 100\,000$). Les $M$ lignes suivantes contiennent chacune une requête. Seules les entrées pour lesquelles le résultat des requêtes est une forêt sont données.

Sortie

Afficher les résultats des requêtes de type 3, un par ligne.

Exemples

Entrée

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

Sortie

0
1
0
1