Mamy las $F$ drzew bez korzeni składający się z $N$ wierzchołków. Początkowo każde drzewo w $F$ składa się tylko z jednego wierzchołka. Wykonujemy następujące zapytania:

• 1 A B: Dodaj krawędź łączącą wierzchołki $A$ i $B$. Przed zapytaniem nie ma krawędzi między $A$ i $B$.
• 2 A B: Usuń krawędź łączącą wierzchołki $A$ i $B$. Przed zapytaniem istnieje krawędź między $A$ i $B$.
• 3 A B: Sprawdź, czy istnieje ścieżka między wierzchołkami $A$ i $B$. Jeśli tak, wypisz $1$, w przeciwnym razie $0$.

Wszystkie $A$ i $B$ spełniają $1 \le A, B \le N$, $A \ne B$, a wszystkie krawędzie są nieskierowane.

Wejście

W pierwszym wierszu podane są liczby całkowite $N$ ($2 \le N \le 100{,}000$) – liczba wierzchołków oraz $M$ ($1 \le M \le 100{,}000$) – liczba zapytań. W kolejnych $M$ wierszach podane są zapytania, po jednym w wierszu. Gwarantuje się, że wszystkie podane dane prowadzą do tego, że po każdym zapytaniu graf pozostaje lasem.

Wyjście

Wypisz wyniki zapytań typu 3, każdy w osobnym wierszu.

Przykład

Wejście 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

Wyjście 1

0
1
0
1