En una galaxia muy lejana hay $N$ estrellas con civilizaciones avanzadas, numeradas del $1$ al $N$. Cada estrella administra una nave espacial. Una nave está en uno de dos estados: en uso para viajar a otra estrella, o sin usar. Si la nave administrada por la estrella $a$ está en uso para viajar a la estrella $b$, realiza viajes de ida y vuelta entre $a$ y $b$ repetidamente. Cuando va de $a$ a $b$, los pasajeros ordinarios pueden subir a ella y viajar de $a$ a $b$. Sin embargo, cuando regresa de $b$ a $a$, no pueden subir, por razones como el combustible o el transporte de carga. Cuando la nave administrada por $a$ está sin usar, permanece en $a$.

Actualmente, todas las naves están sin usar. Ya se ha decidido el calendario de los futuros cambios de estado de las naves. Cada cambio es de uno de los siguientes tipos.

• Poner en uso la nave sin usar administrada por la estrella $a$ para viajar a la estrella $b$. Esto solo se hace cuando un pasajero ordinario no puede viajar de $b$ a $a$ tomando naves espaciales sucesivamente.
• Dejar sin usar la nave que está en uso y que administra la estrella $a$.

Dos personas que planean viajar por esta galaxia han preparado varias preguntas del siguiente tipo para organizar sus encuentros.

• Si, en cierto momento del calendario, una persona está en la estrella $a$ y la otra en la estrella $b$, ¿pueden reunirse utilizando naves espaciales como pasajeros ordinarios? Si pueden, ¿en qué estrella deben reunirse para minimizar el número de viajes en nave espacial? Es decir, ¿existe una estrella $c$ a la que un pasajero ordinario pueda llegar tomando naves sucesivamente tanto desde $a$ como desde $b$? Si existe, ¿qué estrella $c$ minimiza la suma del número de viajes necesarios para ir de $a$ a $c$ y del número de viajes necesarios para ir de $b$ a $c$?

Como excelente programador, te han pedido que respondas todas sus preguntas.

Tarea

Escribe un programa que responda las preguntas, dados los cambios de estado de las naves y las preguntas en orden cronológico.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene los enteros $N,Q$, separados por un espacio. Indican que hay $N$ estrellas y que la suma del número de cambios de estado y del número de preguntas es $Q$.
• Las siguientes $Q$ líneas describen los cambios de estado y las preguntas en orden cronológico. La línea $i$ ($1 \le i \le Q$) contiene dos o tres enteros separados por espacios. Si el primero es $T_i$, se da uno de los siguientes casos.

Caso (i): $T_i=1$

La línea contiene los enteros $T_i,A_i,B_i$ y representa el siguiente cambio de estado: poner en uso la nave administrada por la estrella $A_i$ para viajar a la estrella $B_i$.

Se garantiza que $1 \le A_i \le N$, $1 \le B_i \le N$ y $A_i \ne B_i$; que en ese momento la nave administrada por $A_i$ está sin usar; y que en ese momento un pasajero ordinario no puede viajar de $B_i$ a $A_i$ tomando naves espaciales sucesivamente.

Caso (ii): $T_i=2$

La línea contiene los enteros $T_i,A_i$ y representa el siguiente cambio de estado: dejar sin usar la nave administrada por la estrella $A_i$.

Se garantiza que $1 \le A_i \le N$ y que en ese momento la nave administrada por $A_i$ está en uso.

Caso (iii): $T_i=3$

La línea contiene los enteros $T_i,A_i,B_i$ y representa la siguiente pregunta: si en ese momento una persona está en la estrella $A_i$ y la otra en la estrella $B_i$, ¿pueden reunirse utilizando naves espaciales como pasajeros ordinarios? Si pueden, ¿en qué estrella deben reunirse para minimizar el número de viajes en nave espacial?

Se garantiza que $1 \le A_i \le N$, $1 \le B_i \le N$ y $A_i \ne B_i$.

Salida

Para cada pregunta, escribe en la salida estándar, en orden y en una línea independiente:

• Si pueden reunirse, el número de la estrella en la que deben reunirse para minimizar el número de viajes en nave espacial.
• Si no pueden reunirse, el entero $-1$.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• $2 \le N \le 1\,000\,000$.
• $1 \le Q \le 1\,000\,000$.

Subtareas

Subtarea 1 [10 puntos]

Se cumplen las siguientes condiciones.

• $N \le 5\,000$.
• $Q \le 5\,000$.

Subtarea 2 [30 puntos]

• Se cumple $T_i \ne 2$ ($1 \le i \le Q$).

Subtarea 3 [60 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

6 5
1 2 4
3 2 6
1 4 3
1 6 4
3 2 6

Salida 1

-1
4

Nota

En este ejemplo, los cambios de estado y las preguntas son los siguientes, en este orden.

• La nave administrada por la estrella 2 se pone en uso para viajar a la estrella 4.
• Si en ese momento las dos personas están en las estrellas 2 y 6, no pueden reunirse, por lo que se escribe $-1$.
• La nave administrada por la estrella 4 se pone en uso para viajar a la estrella 3.
• La nave administrada por la estrella 6 se pone en uso para viajar a la estrella 4.
• Si en ese momento las dos personas están en las estrellas 2 y 6, pueden reunirse en la estrella 3 o en la estrella 4. Para minimizar el número de viajes en nave espacial deben reunirse en la estrella 4, por lo que se escribe 4.

Entrada 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

Salida 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6