Lontano nell'universo, c'è una galassia con $N$ pianeti avanzati. I pianeti sono numerati da 1 a $N$. Ogni pianeta gestisce un'astronave. Un'astronave si trova o nello stato di utilizzo per viaggiare verso un altro pianeta, oppure nello stato di inutilizzo. Quando l'astronave gestita dal pianeta $a$ si trova nello stato di utilizzo per viaggiare verso il pianeta $b$, l'astronave viaggia avanti e indietro tra il pianeta $a$ e il pianeta $b$ molte volte. Quando l'astronave viaggia dal pianeta $a$ al pianeta $b$, i passeggeri comuni possono salire a bordo dell'astronave per viaggiare dal pianeta $a$ al pianeta $b$. Tuttavia, quando l'astronave ritorna dal pianeta $b$ al pianeta $a$, i passeggeri comuni non possono salire a bordo a causa di problemi di carburante o vincoli di carico. Inoltre, quando l'astronave gestita dal pianeta $a$ si trova nello stato di inutilizzo, rimane in attesa sul pianeta $a$.

Attualmente, tutte le astronavi si trovano nello stato di inutilizzo. È stato stabilito un programma per i futuri cambiamenti di stato delle astronavi. I cambiamenti di stato sono dei seguenti tipi:

• Portare l'astronave gestita dal pianeta $a$ (che attualmente si trova nello stato di inutilizzo) nello stato di utilizzo per viaggiare verso il pianeta $b$. Si noti che ciò avviene solo quando per i passeggeri comuni è impossibile viaggiare dal pianeta $b$ al pianeta $a$ prendendo più astronavi in successione.
• Portare l'astronave gestita dal pianeta $a$ (che attualmente si trova nello stato di utilizzo) nello stato di inutilizzo.

Due persone che progettano di viaggiare attraverso questa galassia hanno preparato diverse domande della forma seguente per pianificare il loro incontro:

• In un certo istante del programma, supponiamo che una persona si trovi sul pianeta $a$ e l'altra sul pianeta $b$. Possono le due persone incontrarsi utilizzando le astronavi come passeggeri comuni? Inoltre, se possono incontrarsi, su quale pianeta dovrebbero incontrarsi affinché il numero complessivo di utilizzi di un'astronave sia minimo? Cioè, esiste un pianeta $c$ tale che i passeggeri comuni possano viaggiare dal pianeta $a$ al pianeta $c$ e dal pianeta $b$ al pianeta $c$ prendendo più astronavi? Se un tale pianeta esiste, quale pianeta $c$ minimizza la somma tra il numero di volte in cui viene usata un'astronave per viaggiare dal pianeta $a$ al pianeta $c$ e il numero di volte in cui viene usata un'astronave per viaggiare dal pianeta $b$ al pianeta $c$?

A te, eccellente programmatore, è stato chiesto di trovare le risposte a tutte le loro domande.

Dati di input

Leggi i seguenti dati dallo standard input:

• La prima riga contiene due interi $N$ e $Q$, separati da uno spazio, che rappresentano il numero di pianeti $N$ e il numero totale di cambiamenti di stato e domande $Q$.
• Le successive $Q$ righe rappresentano i cambiamenti di stato e le domande in ordine cronologico. La $i$-esima riga ($1 \le i \le Q$) contiene due o tre interi separati da spazi. Sia $T_i$ il primo intero. Esso assume uno dei seguenti valori:

(i) Se $T_i = 1$: Questa riga contiene gli interi $T_i, A_i, B_i$, che rappresentano il seguente cambiamento di stato: portare l'astronave gestita dal pianeta $A_i$ nello stato di utilizzo per viaggiare verso il pianeta $B_i$. È garantito che $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, che l'astronave gestita dal pianeta $A_i$ si trova attualmente nello stato di inutilizzo e che, in questo momento, è impossibile per i passeggeri comuni viaggiare dal pianeta $B_i$ al pianeta $A_i$ prendendo più astronavi.

(ii) Se $T_i = 2$: Questa riga contiene gli interi $T_i, A_i$, che rappresentano il seguente cambiamento di stato: portare l'astronave gestita dal pianeta $A_i$ nello stato di inutilizzo. È garantito che $1 \le A_i \le N$ e che l'astronave gestita dal pianeta $A_i$ si trova attualmente nello stato di utilizzo.

(iii) Se $T_i = 3$: Questa riga contiene gli interi $T_i, A_i, B_i$, che rappresentano la seguente domanda: in questo momento, se una persona si trova sul pianeta $A_i$ e l'altra si trova sul pianeta $B_i$, possono incontrarsi utilizzando le astronavi come passeggeri comuni? Se possono incontrarsi, quale pianeta $c$ minimizza il numero di utilizzi di astronavi? È garantito che $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Dati di output

Per ciascuna domanda, stampa quanto segue sullo standard output su una nuova riga:

• Se possono incontrarsi, il numero del pianeta in cui dovrebbero incontrarsi per minimizzare il numero di utilizzi di astronavi.
• Se non possono incontrarsi, l'intero -1.

Limiti

Tutti i dati di input soddisfano le seguenti condizioni:

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

Sottoproblemi

Sottoproblema 1 [10 punti]

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

Sottoproblema 2 [30 punti]

• $T_i \neq 2$ ($1 \le i \le Q$).

Sottoproblema 3 [60 punti]

• Nessuna limitazione aggiuntiva.

Esempi

Input 1

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

Output 1

-1
4

Nota 1

In questo esempio, i cambiamenti di stato e le domande avvengono nel seguente ordine:

• L'astronave gestita dal pianeta 2 entra nello stato di utilizzo per viaggiare verso il pianeta 4.
• A questo punto, se due persone si trovano sul pianeta 2 e sul pianeta 6, non possono incontrarsi, quindi si stampa -1.
• L'astronave gestita dal pianeta 4 entra nello stato di utilizzo per viaggiare verso il pianeta 3.
• L'astronave gestita dal pianeta 6 entra nello stato di utilizzo per viaggiare verso il pianeta 4.
• A questo punto, se due persone si trovano sul pianeta 2 e sul pianeta 6, possono incontrarsi sul pianeta 3 oppure sul pianeta 4. Per minimizzare il numero di utilizzi di astronavi, dovrebbero incontrarsi sul pianeta 4, quindi si stampa 4.

Input 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

Output 2

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