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

Напишите программу, обрабатывающую следующие запросы:

• 1 u v: соединить ребром вершины $u$ и $v$. При этом $v$ становится родителем $u$. Гарантируется, что до выполнения запроса $u$ является корнем дерева, содержащего $u$, и что $u$ и $v$ находятся в разных деревьях.
• 2 v: удалить ребро, соединяющее $v$ и его родителя. $v$ не является корнем.
• 3 u v: вывести LCA вершин $u$ и $v$. $u$ и $v$ находятся в одном дереве.

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

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

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

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

Примеры

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

5 9
3 1 1
1 1 2
1 3 2
1 4 3
3 1 4
3 3 4
2 4
1 5 3
3 1 5

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

1
2
3
2