Имеется лес $F$ из некорневых деревьев, состоящих из $N$ вершин. Изначально каждое дерево в $F$ состоит из одной вершины. Выполним следующие запросы:

• 1 A B: добавить ребро, соединяющее вершины $A$ и $B$. До выполнения запроса между $A$ и $B$ нет ребра.
• 2 A B: удалить ребро, соединяющее вершины $A$ и $B$. До выполнения запроса между $A$ и $B$ есть ребро.
• 3 A B: проверить, существует ли путь из вершины $A$ в вершину $B$. Если да, вывести $1$, в противном случае — $0$.

Все $A$ и $B$ удовлетворяют условиям $1 \le A, B \le N$, $A \ne B$, и все рёбра неориентированные.

Входные данные

В первой строке заданы количество вершин $N$ ($2 \le N \le 100{,}000$) и количество запросов $M$ ($1 \le M \le 100{,}000$). В следующих $M$ строках заданы запросы, по одному на строку. Гарантируется, что после выполнения каждого запроса множество рёбер образует лес.

Выходные данные

Для каждого запроса типа 3 выведите результат на отдельной строке.

Примеры

Входные данные

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

Выходные данные

0
1
0
1