Långt borta i universum finns en galax med $N$ avancerade planeter. Planeterna är numrerade från 1 till $N$. Varje planet förvaltar ett rymdskepp. Ett rymdskepp är antingen i ett tillstånd där det används för att resa till en annan planet, eller i ett oanvänt tillstånd. När rymdskeppet som förvaltas av planet $a$ är i tillståndet att användas för att resa till planet $b$, reser rymdskeppet fram och tillbaka mellan planet $a$ och planet $b$ många gånger. När rymdskeppet reser från planet $a$ till planet $b$ kan vanliga passagerare gå ombord på rymdskeppet för att resa från planet $a$ till planet $b$. När rymdskeppet däremot återvänder från planet $b$ till planet $a$ kan vanliga passagerare inte gå ombord på grund av bränsleproblem eller lastbegränsningar. När rymdskeppet som förvaltas av planet $a$ är i det oanvända tillståndet väntar det dessutom på planet $a$.

För närvarande är alla rymdskepp i det oanvända tillståndet. Ett schema för framtida ändringar i rymdskeppens tillstånd har fastställts. Tillståndsändringarna är av följande typer:

• Ändra rymdskeppet som förvaltas av planet $a$ (som för närvarande är i det oanvända tillståndet) till tillståndet att användas för att resa till planet $b$. Observera att detta endast sker när det är omöjligt för vanliga passagerare att resa från planet $b$ till planet $a$ genom att gå ombord på rymdskepp flera gånger.
• Ändra rymdskeppet som förvaltas av planet $a$ (som för närvarande är i det använda tillståndet) till det oanvända tillståndet.

Två personer som planerar att resa genom denna galax har förberett flera frågor av följande form för att planera sitt möte:

• Antag att vid en viss tidpunkt i schemat befinner sig den ena personen på planet $a$ och den andra på planet $b$. Kan de två personerna mötas genom att använda rymdskepp som vanliga passagerare? Vidare, om de kan mötas, på vilken planet skulle de mötas så att antalet gånger de använder ett rymdskepp minimeras? Det vill säga, finns det en planet $c$ sådan att vanliga passagerare kan resa från planet $a$ till planet $c$ och från planet $b$ till planet $c$ genom att gå ombord på rymdskepp flera gånger? Om en sådan planet finns, vilken planet $c$ minimerar summan av antalet gånger ett rymdskepp används för att resa från planet $a$ till planet $c$ och antalet gånger ett rymdskepp används för att resa från planet $b$ till planet $c$?

Du, en skicklig programmerare, har blivit ombedd att hitta svaren på alla deras frågor.

Indata

Läs följande från standard in:

• Den första raden innehåller två heltal $N$ och $Q$, separerade med ett mellanslag, vilka representerar antalet planeter $N$ samt det totala antalet tillståndsändringar och frågor $Q$.
• De följande $Q$ raderna representerar tillståndsändringarna och frågorna i kronologisk ordning. Den $i$-te raden ($1 \le i \le Q$) innehåller två eller tre heltal separerade med mellanslag. Låt det första heltalet vara $T_i$. Det är ett av följande:

(i) Om $T_i = 1$: Denna rad innehåller heltalen $T_i, A_i, B_i$, vilka representerar följande tillståndsändring: ändra rymdskeppet som förvaltas av planet $A_i$ till tillståndet att användas för att resa till planet $B_i$. Det garanteras att $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, att rymdskeppet som förvaltas av planet $A_i$ för närvarande är i det oanvända tillståndet, och att det i detta ögonblick är omöjligt för vanliga passagerare att resa från planet $B_i$ till planet $A_i$ genom att gå ombord på rymdskepp flera gånger.

(ii) Om $T_i = 2$: Denna rad innehåller heltalen $T_i, A_i$, vilka representerar följande tillståndsändring: ändra rymdskeppet som förvaltas av planet $A_i$ till det oanvända tillståndet. Det garanteras att $1 \le A_i \le N$, och att rymdskeppet som förvaltas av planet $A_i$ för närvarande är i det använda tillståndet.

(iii) Om $T_i = 3$: Denna rad innehåller heltalen $T_i, A_i, B_i$, vilka representerar följande fråga: i detta ögonblick, om den ena personen är på planet $A_i$ och den andra är på planet $B_i$, kan de mötas genom att använda rymdskepp som vanliga passagerare? Om de kan mötas, vilken planet $c$ minimerar antalet rymdskeppsresor? Det garanteras att $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Utdata

För varje fråga, skriv ut följande till standard ut på en ny rad:

• Om de kan mötas, numret på den planet där de bör mötas för att minimera antalet rymdskeppsresor.
• Om de inte kan mötas, heltalet -1.

Begränsningar

All indata uppfyller följande villkor:

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

Deluppgifter

Deluppgift 1 [10 poäng]

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

Deluppgift 2 [30 poäng]

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

Deluppgift 3 [60 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

-1
4

Anmärkning 1

I detta exempel sker tillståndsändringarna och frågorna i följande ordning:

• Rymdskeppet som förvaltas av planet 2 går in i tillståndet att användas för att resa till planet 4.
• Vid denna tidpunkt, om två personer befinner sig på planet 2 och planet 6, kan de inte mötas, så skriv ut -1.
• Rymdskeppet som förvaltas av planet 4 går in i tillståndet att användas för att resa till planet 3.
• Rymdskeppet som förvaltas av planet 6 går in i tillståndet att användas för att resa till planet 4.
• Vid denna tidpunkt, om två personer befinner sig på planet 2 och planet 6, kan de mötas på planet 3 eller planet 4. För att minimera antalet rymdskeppsresor bör de mötas på planet 4, så skriv ut 4.

Indata 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