Hay un bosque $F$ de árboles sin raíz compuesto por $N$ vértices. Inicialmente, todos los árboles en $F$ son árboles que consisten en un solo vértice. Realicemos las siguientes consultas:

• 1 A B: Agrega una arista que conecta los vértices $A$ y $B$. Antes de la consulta no hay arista entre $A$ y $B$.
• 2 A B: Elimina la arista que conecta los vértices $A$ y $B$. Antes de la consulta existe una arista entre $A$ y $B$.
• 3 A B: Verifica si existe un camino desde $A$ hasta $B$. Si existe, imprime $1$; si no, imprime $0$.

Todos los $A$ y $B$ satisfacen $1 \le A, B \le N$, $A \ne B$, y todas las aristas no tienen dirección.

Entrada

En la primera línea se dan el número de vértices $N$ ($2 \le N \le 100{,}000$) y el número de consultas $M$ ($1 \le M \le 100{,}000$). En las siguientes $M$ líneas se dan las consultas, una por línea. Solo se dan entradas donde el resultado de las consultas es un bosque.

Salida

Se imprime el resultado de las consultas de tipo 3, una por línea.

Ejemplos

Entrada 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

Salida 1

0
1
0
1