Kaukana maailmankaikkeudessa on galaksi, jossa on $N$ kehittynyttä planeettaa. Planeetat on numeroitu 1:stä $N$:ään. Jokainen planeetta hallinnoi yhtä avaruusalusta. Avaruusalus on joko tilassa, jossa sitä käytetään matkustamiseen toiselle planeetalle, tai käyttämättömässä tilassa. Kun planeetan $a$ hallinnoima avaruusalus on tilassa, jossa sitä käytetään matkustamiseen planeetalle $b$, avaruusalus kulkee edestakaisin planeetan $a$ ja planeetan $b$ välillä lukuisia kertoja. Kun avaruusalus matkustaa planeetalta $a$ planeetalle $b$, tavalliset matkustajat voivat nousta avaruusalukseen matkustaakseen planeetalta $a$ planeetalle $b$. Kun avaruusalus kuitenkin palaa planeetalta $b$ planeetalle $a$, tavalliset matkustajat eivät voi nousta kyytiin polttoaineongelmien tai rahtirajoitusten vuoksi. Lisäksi, kun planeetan $a$ hallinnoima avaruusalus on käyttämättömässä tilassa, se odottaa planeetalla $a$.

Tällä hetkellä kaikki avaruusalukset ovat käyttämättömässä tilassa. Avaruusalusten tuleville tilanmuutoksille on laadittu aikataulu. Tilanmuutokset ovat seuraavanlaisia:

• Muuta planeetan $a$ hallinnoima avaruusalus (joka on tällä hetkellä käyttämättömässä tilassa) tilaan, jossa sitä käytetään matkustamiseen planeetalle $b$. Huomaa, että tämä tapahtuu vain silloin, kun tavallisten matkustajien on mahdotonta matkustaa planeetalta $b$ planeetalle $a$ nousemalla avaruusaluksiin useita kertoja.
• Muuta planeetan $a$ hallinnoima avaruusalus (joka on tällä hetkellä käytössä olevassa tilassa) käyttämättömään tilaan.

Kaksi henkilöä, jotka suunnittelevat matkustavansa tämän galaksin halki, ovat laatineet useita seuraavanmuotoisia kysymyksiä tapaamisensa suunnittelemiseksi:

• Oletetaan, että tietyllä hetkellä aikataulussa toinen henkilö on planeetalla $a$ ja toinen planeetalla $b$. Voivatko nämä kaksi henkilöä tavata käyttämällä avaruusaluksia tavallisina matkustajina? Lisäksi, jos he voivat tavata, millä planeetalla heidän tulisi tavata, jotta avaruusalusten käyttökertojen määrä olisi mahdollisimman pieni? Toisin sanoen, onko olemassa planeettaa $c$ siten, että tavalliset matkustajat voivat matkustaa planeetalta $a$ planeetalle $c$ ja planeetalta $b$ planeetalle $c$ nousemalla avaruusaluksiin useita kertoja? Jos tällainen planeetta on olemassa, mikä planeetta $c$ minimoi planeetalta $a$ planeetalle $c$ matkustamiseen tarvittavien avaruusalusten käyttökertojen ja planeetalta $b$ planeetalle $c$ matkustamiseen tarvittavien avaruusalusten käyttökertojen summan?

Sinua, erinomaista ohjelmoijaa, on pyydetty etsimään vastaukset kaikkiin heidän kysymyksiinsä.

Syöte

Lue standardisyötteestä seuraavat tiedot:

• Ensimmäisellä rivillä on kaksi välilyönnillä erotettua kokonaislukua $N$ ja $Q$, jotka ilmaisevat planeettojen lukumäärää $N$ sekä tilanmuutosten ja kysymysten kokonaismäärää $Q$.
• Seuraavat $Q$ riviä kuvaavat tilanmuutokset ja kysymykset aikajärjestyksessä. Rivillä $i$ ($1 \le i \le Q$) on kaksi tai kolme välilyönnein erotettua kokonaislukua. Olkoon ensimmäinen kokonaisluku $T_i$. Se on jokin seuraavista:

(i) Jos $T_i = 1$: Tällä rivillä on kokonaisluvut $T_i, A_i, B_i$, jotka kuvaavat seuraavaa tilanmuutosta: muuta planeetan $A_i$ hallinnoima avaruusalus tilaan, jossa sitä käytetään matkustamiseen planeetalle $B_i$. On taattua, että $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$, että planeetan $A_i$ hallinnoima avaruusalus on tällä hetkellä käyttämättömässä tilassa ja että tällä hetkellä tavallisten matkustajien on mahdotonta matkustaa planeetalta $B_i$ planeetalle $A_i$ nousemalla avaruusaluksiin useita kertoja.

(ii) Jos $T_i = 2$: Tällä rivillä on kokonaisluvut $T_i, A_i$, jotka kuvaavat seuraavaa tilanmuutosta: muuta planeetan $A_i$ hallinnoima avaruusalus käyttämättömään tilaan. On taattua, että $1 \le A_i \le N$ ja että planeetan $A_i$ hallinnoima avaruusalus on tällä hetkellä käytössä olevassa tilassa.

(iii) Jos $T_i = 3$: Tällä rivillä on kokonaisluvut $T_i, A_i, B_i$, jotka kuvaavat seuraavaa kysymystä: jos tällä hetkellä toinen henkilö on planeetalla $A_i$ ja toinen planeetalla $B_i$, voivatko he tavata käyttämällä avaruusaluksia tavallisina matkustajina? Jos he voivat tavata, mikä planeetta $c$ minimoi avaruusalusten käyttökertojen määrän? On taattua, että $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \neq B_i$.

Tuloste

Tulosta jokaista kysymystä kohden standarditulosteeseen omalle rivilleen seuraavaa:

• Jos he voivat tavata, sen planeetan numero, jolla heidän tulisi tavata avaruusalusten käyttökertojen minimoimiseksi.
• Jos he eivät voi tavata, kokonaisluku -1.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

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

Osatehtävät

Osatehtävä 1 [10 pistettä]

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

Osatehtävä 2 [30 pistettä]

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

Osatehtävä 3 [60 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

-1
4

Huomautus 1

Tässä esimerkissä tilanmuutokset ja kysymykset tapahtuvat seuraavassa järjestyksessä:

• Planeetan 2 hallinnoima avaruusalus siirtyy tilaan, jossa sitä käytetään matkustamiseen planeetalle 4.
• Tällä hetkellä, jos kaksi henkilöä ovat planeetalla 2 ja planeetalla 6, he eivät voi tavata, joten tulostetaan -1.
• Planeetan 4 hallinnoima avaruusalus siirtyy tilaan, jossa sitä käytetään matkustamiseen planeetalle 3.
• Planeetan 6 hallinnoima avaruusalus siirtyy tilaan, jossa sitä käytetään matkustamiseen planeetalle 4.
• Tällä hetkellä, jos kaksi henkilöä ovat planeetalla 2 ja planeetalla 6, he voivat tavata planeetalla 3 tai planeetalla 4. Avaruusalusten käyttökertojen minimoimiseksi heidän tulisi tavata planeetalla 4, joten tulostetaan 4.

Syöte 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

Tuloste 2

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