Istnieje $N$ ukorzenionych drzew, każde składające się z pojedynczego wierzchołka. Wierzchołki są ponumerowane od $1$ do $N$.

Napisz program wykonujący następujące zapytania:

• 1 u v: Połącz krawędzią wierzchołki $u$ i $v$. Wtedy $v$ staje się rodzicem $u$. Przed wykonaniem zapytania $u$ jest korzeniem drzewa, do którego należy, oraz gwarantuje się, że $u$ i $v$ należą do różnych drzew.
• 2 v: Usuń krawędź łączącą $v$ z jego rodzicem. $v$ nie jest korzeniem.
• 3 u v: Wypisz LCA (najniższego wspólnego przodka) wierzchołków $u$ i $v$. $u$ i $v$ znajdują się w tym samym drzewie.

Wejście

W pierwszym wierszu dane są $N$ ($2 \le N \le 100{,}000$) oraz liczba zapytań $M$ ($1 \le M \le 200{,}000$).

W kolejnych $M$ wierszach znajdują się zapytania, każde w osobnym wierszu.

Wyjście

Wypisz wyniki dla każdego zapytania typu 3, po jednym w wierszu, w kolejności występowania.

Przykład

Wejście

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

Wyjście

1
2
3
2