Hay $N$ árboles enraizados, cada uno formado por un único vértice. Los vértices están numerados del $1$ al $N$.

Escriba un programa que procese las siguientes consultas:

• 1 u v: Conecta una arista entre $u$ y $v$. En este caso, $v$ se convierte en el padre de $u$. Antes de ejecutar la consulta, $u$ es la raíz del árbol que contiene a $u$, y se garantiza que $u$ y $v$ pertenecen a árboles diferentes.
• 2 v: Elimina la arista que conecta a $v$ con su padre. $v$ no es la raíz.
• 3 u v: Imprime el LCA de $u$ y $v$. $u$ y $v$ están en el mismo árbol.

Entrada

En la primera línea se dan $N$ ($2 \le N \le 100{,}000$) y el número de consultas $M$ ($1 \le M \le 200{,}000$).

En las siguientes $M$ líneas se dan las consultas, una por línea.

Salida

Para cada consulta de tipo 3, imprime el resultado en una línea separada en el orden en que aparecen.

Ejemplos

Entrada

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

Salida

1
2
3
2