Langt úti í geimnum er vetrarbraut með $N$ þróuðum reikistjörnum. Reikistjörnurnar eru númeraðar frá 1 til $N$. Hver reikistjarna hefur umsjón með einu geimfari. Geimfar er annaðhvort í því ástandi að vera notað til ferðalaga til annarrar reikistjörnu, eða í ónotuðu ástandi. Þegar geimfarið sem reikistjarna $a$ hefur umsjón með er í því ástandi að vera notað til að ferðast til reikistjörnu $b$, ferðast geimfarið fram og til baka milli reikistjörnu $a$ og reikistjörnu $b$ mörgum sinnum. Þegar geimfarið ferðast frá reikistjörnu $a$ til reikistjörnu $b$ geta almennir farþegar farið um borð í geimfarið til að ferðast frá reikistjörnu $a$ til reikistjörnu $b$. Hins vegar, þegar geimfarið snýr til baka frá reikistjörnu $b$ til reikistjörnu $a$, geta almennir farþegar ekki farið um borð vegna eldsneytisvandamála eða farmskorðana. Einnig, þegar geimfarið sem reikistjarna $a$ hefur umsjón með er í ónotuðu ástandi, bíður það á reikistjörnu $a$.

Eins og er eru öll geimför í ónotuðu ástandi. Áætlun um framtíðarbreytingar á ástandi geimfaranna hefur verið ákveðin. Ástandsbreytingarnar eru af eftirfarandi gerðum:

• Breyta geimfarinu sem reikistjarna $a$ hefur umsjón með (sem er nú í ónotuðu ástandi) í það ástand að vera notað til að ferðast til reikistjörnu $b$. Athugið að þetta gerist aðeins þegar ómögulegt er fyrir almenna farþega að ferðast frá reikistjörnu $b$ til reikistjörnu $a$ með því að fara um borð í geimför mörgum sinnum.
• Breyta geimfarinu sem reikistjarna $a$ hefur umsjón með (sem er nú í notuðu ástandi) í ónotað ástand.

Tveir einstaklingar sem ætla að ferðast um þessa vetrarbraut hafa undirbúið nokkrar spurningar á eftirfarandi formi til að skipuleggja fund sinn:

• Gerum ráð fyrir að á ákveðnum tímapunkti í áætluninni sé annar einstaklingurinn á reikistjörnu $a$ og hinn á reikistjörnu $b$. Geta einstaklingarnir tveir hist með því að nota geimför sem almennir farþegar? Enn fremur, ef þeir geta hist, á hvaða reikistjörnu myndu þeir hittast þannig að fjöldi skipta sem þeir nota geimfar sé lágmarkaður? Það er að segja, er til reikistjarna $c$ þannig að almennir farþegar geti ferðast frá reikistjörnu $a$ til reikistjörnu $c$ og frá reikistjörnu $b$ til reikistjörnu $c$ með því að fara um borð í geimför mörgum sinnum? Ef slík reikistjarna er til, hvaða reikistjarna $c$ lágmarkar summu fjölda skipta sem geimfar er notað til að ferðast frá reikistjörnu $a$ til reikistjörnu $c$ og fjölda skipta sem geimfar er notað til að ferðast frá reikistjörnu $b$ til reikistjörnu $c$?

Þú, sem framúrskarandi forritari, hefur verið beðinn um að finna svörin við öllum spurningum þeirra.

Inntak

Lestu eftirfarandi af staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $Q$, aðskildar með bili, sem tákna fjölda reikistjarna $N$ og heildarfjölda ástandsbreytinga og spurninga $Q$.
• Næstu $Q$ línur tákna ástandsbreytingarnar og spurningarnar í tímaröð. $i$-ta línan ($1 \le i \le Q$) inniheldur tvær eða þrjár heiltölur aðskildar með bilum. Látum fyrstu heiltöluna vera $T_i$. Hún er eitt af eftirfarandi:

(i) Ef $T_i = 1$: Þessi lína inniheldur heiltölurnar $T_i, A_i, B_i$, sem tákna eftirfarandi ástandsbreytingu: breyta geimfarinu sem reikistjarna $A_i$ hefur umsjón með í það ástand að vera notað til að ferðast til reikistjörnu $B_i$. Tryggt er að $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, að geimfarið sem reikistjarna $A_i$ hefur umsjón með sé nú í ónotuðu ástandi, og að á þessari stundu sé ómögulegt fyrir almenna farþega að ferðast frá reikistjörnu $B_i$ til reikistjörnu $A_i$ með því að fara um borð í geimför mörgum sinnum.

(ii) Ef $T_i = 2$: Þessi lína inniheldur heiltölurnar $T_i, A_i$, sem tákna eftirfarandi ástandsbreytingu: breyta geimfarinu sem reikistjarna $A_i$ hefur umsjón með í ónotað ástand. Tryggt er að $1 \le A_i \le N$, og að geimfarið sem reikistjarna $A_i$ hefur umsjón með sé nú í notuðu ástandi.

(iii) Ef $T_i = 3$: Þessi lína inniheldur heiltölurnar $T_i, A_i, B_i$, sem tákna eftirfarandi spurningu: á þessari stundu, ef annar einstaklingurinn er á reikistjörnu $A_i$ og hinn á reikistjörnu $B_i$, geta þeir hist með því að nota geimför sem almennir farþegar? Ef þeir geta hist, hvaða reikistjarna $c$ lágmarkar fjölda geimfaranotkana? Tryggt er að $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Úttak

Fyrir hverja spurningu skaltu skrifa eftirfarandi á staðalúttak í nýrri línu:

• Ef þeir geta hist, númer reikistjörnunnar þar sem þeir ættu að hittast til að lágmarka fjölda geimfaranotkana.
• Ef þeir geta ekki hist, heiltöluna -1.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

Undirverkefni 1 [10 stig]

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

Undirverkefni 2 [30 stig]

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

Undirverkefni 3 [60 stig]

• Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

-1
4

Athugasemd 1

Í þessu dæmi eiga ástandsbreytingarnar og spurningarnar sér stað í eftirfarandi röð:

• Geimfarið sem reikistjarna 2 hefur umsjón með fer í það ástand að vera notað til að ferðast til reikistjörnu 4.
• Á þessum tímapunkti, ef tveir einstaklingar eru á reikistjörnu 2 og reikistjörnu 6, geta þeir ekki hist, svo skrifað er út -1.
• Geimfarið sem reikistjarna 4 hefur umsjón með fer í það ástand að vera notað til að ferðast til reikistjörnu 3.
• Geimfarið sem reikistjarna 6 hefur umsjón með fer í það ástand að vera notað til að ferðast til reikistjörnu 4.
• Á þessum tímapunkti, ef tveir einstaklingar eru á reikistjörnu 2 og reikistjörnu 6, geta þeir hist á reikistjörnu 3 eða reikistjörnu 4. Til að lágmarka fjölda geimfaranotkana ættu þeir að hittast á reikistjörnu 4, svo skrifað er út 4.

Inntak 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

Úttak 2

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