Langt borte i universet finnes det en galakse med $N$ avanserte planeter. Planetene er nummerert fra 1 til $N$. Hver planet administrerer ett romskip. Et romskip er enten i en tilstand der det brukes til å reise til en annen planet, eller i en ubrukt tilstand. Når romskipet administrert av planet $a$ er i tilstanden der det brukes til å reise til planet $b$, reiser romskipet frem og tilbake mellom planet $a$ og planet $b$ mange ganger. Når romskipet reiser fra planet $a$ til planet $b$, kan vanlige passasjerer gå om bord i romskipet for å reise fra planet $a$ til planet $b$. Når romskipet returnerer fra planet $b$ til planet $a$, kan imidlertid ikke vanlige passasjerer gå om bord på grunn av drivstoffproblemer eller lastebegrensninger. Når romskipet administrert av planet $a$ er i den ubrukte tilstanden, venter det dessuten på planet $a$.

For øyeblikket er alle romskipene i den ubrukte tilstanden. En tidsplan for fremtidige endringer i romskipenes tilstand har blitt fastsatt. Tilstandsendringene er av følgende typer:

• Endre romskipet administrert av planet $a$ (som for øyeblikket er i den ubrukte tilstanden) til tilstanden der det brukes til å reise til planet $b$. Merk at dette bare skjer når det er umulig for vanlige passasjerer å reise fra planet $b$ til planet $a$ ved å gå om bord i romskip flere ganger.
• Endre romskipet administrert av planet $a$ (som for øyeblikket er i den brukte tilstanden) til den ubrukte tilstanden.

To personer som planlegger å reise gjennom denne galaksen har forberedt flere spørsmål på følgende form for å planlegge møtet sitt:

• Anta at på et bestemt tidspunkt i tidsplanen er den ene personen på planet $a$ og den andre på planet $b$. Kan de to personene møtes ved å bruke romskip som vanlige passasjerer? Videre, hvis de kan møtes, på hvilken planet bør de møtes slik at antall ganger de bruker et romskip minimeres? Det vil si, finnes det en planet $c$ slik at vanlige passasjerer kan reise fra planet $a$ til planet $c$ og fra planet $b$ til planet $c$ ved å gå om bord i romskip flere ganger? Hvis en slik planet finnes, hvilken planet $c$ minimerer summen av antall ganger et romskip brukes for å reise fra planet $a$ til planet $c$ og antall ganger et romskip brukes for å reise fra planet $b$ til planet $c$?

Du, en utmerket programmerer, har blitt bedt om å finne svarene på alle spørsmålene deres.

Inndata

Les følgende fra standard inndata:

• Den første linjen inneholder to heltall $N$ og $Q$, atskilt med et mellomrom, som representerer antall planeter $N$ og det totale antallet tilstandsendringer og spørsmål $Q$.
• De påfølgende $Q$ linjene representerer tilstandsendringene og spørsmålene i kronologisk rekkefølge. Den $i$-te linjen ($1 \le i \le Q$) inneholder to eller tre heltall atskilt med mellomrom. La det første heltallet være $T_i$. Det er ett av følgende:

(i) Hvis $T_i = 1$: Denne linjen inneholder heltallene $T_i, A_i, B_i$, som representerer følgende tilstandsendring: endre romskipet administrert av planet $A_i$ til tilstanden der det brukes til å reise til planet $B_i$. Det er garantert at $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, at romskipet administrert av planet $A_i$ for øyeblikket er i den ubrukte tilstanden, og at det i dette øyeblikket er umulig for vanlige passasjerer å reise fra planet $B_i$ til planet $A_i$ ved å gå om bord i romskip flere ganger.

(ii) Hvis $T_i = 2$: Denne linjen inneholder heltallene $T_i, A_i$, som representerer følgende tilstandsendring: endre romskipet administrert av planet $A_i$ til den ubrukte tilstanden. Det er garantert at $1 \le A_i \le N$, og at romskipet administrert av planet $A_i$ for øyeblikket er i den brukte tilstanden.

(iii) Hvis $T_i = 3$: Denne linjen inneholder heltallene $T_i, A_i, B_i$, som representerer følgende spørsmål: i dette øyeblikket, hvis den ene personen er på planet $A_i$ og den andre er på planet $B_i$, kan de møtes ved å bruke romskip som vanlige passasjerer? Hvis de kan møtes, hvilken planet $c$ minimerer antall romskipbruk? Det er garantert at $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Utdata

For hvert spørsmål, skriv ut følgende til standard utdata på en ny linje:

• Hvis de kan møtes, nummeret på planeten der de bør møtes for å minimere antall romskipbruk.
• Hvis de ikke kan møtes, heltallet -1.

Begrensninger

Alle inndata oppfyller følgende betingelser:

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

Deloppgaver

Deloppgave 1 [10 poeng]

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

Deloppgave 2 [30 poeng]

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

Deloppgave 3 [60 poeng]

• Ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

-1
4

Merk 1

I dette eksempelet skjer tilstandsendringene og spørsmålene i følgende rekkefølge:

• Romskipet administrert av planet 2 går inn i tilstanden der det brukes til å reise til planet 4.
• På dette tidspunktet, hvis to personer er på planet 2 og planet 6, kan de ikke møtes, så skriv ut -1.
• Romskipet administrert av planet 4 går inn i tilstanden der det brukes til å reise til planet 3.
• Romskipet administrert av planet 6 går inn i tilstanden der det brukes til å reise til planet 4.
• På dette tidspunktet, hvis to personer er på planet 2 og planet 6, kan de møtes på planet 3 eller planet 4. For å minimere antall romskipbruk bør de møtes på planet 4, så skriv ut 4.

Inndata 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

Utdata 2

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