Daleko w kosmosie, w pewnej galaktyce, istnieje $N$ planet o rozwiniętej cywilizacji. Planety są ponumerowane od $1$ do $N$. Każda zarządza jednym statkiem kosmicznym. Statek jest albo używany do podróży na pewną inną planetę, albo nieużywany. Jeśli statek zarządzany przez planetę $a$ jest używany do podróży na planetę $b$, wielokrotnie kursuje między $a$ i $b$. Zwykli pasażerowie mogą nim podróżować z $a$ do $b$, lecz podczas powrotu z $b$ do $a$ nie mogą wsiadać ze względu na paliwo, przewóz ładunków i inne okoliczności. Gdy statek planety $a$ nie jest używany, czeka na planecie $a$.

Obecnie wszystkie statki są nieużywane. Ustalono harmonogram przyszłych zmian ich stanów. Każda zmiana jest jednego z następujących typów:

• Nieużywany statek zarządzany przez planetę $a$ zaczyna być używany do podróży na planetę $b$. Taka zmiana jest wykonywana tylko wtedy, gdy zwykły pasażer nie może dotrzeć z $b$ do $a$, korzystając z pewnej liczby przelotów statkami.
• Używany statek zarządzany przez planetę $a$ przestaje być używany.

Dwie osoby planujące podróż po tej galaktyce przygotowały kilka pytań następującego rodzaju, aby zaplanować spotkanie:

• Jeśli w danym momencie harmonogramu jedna osoba jest na planecie $a$, a druga na planecie $b$, czy mogą spotkać się, podróżując statkami jako zwykli pasażerowie? Jeśli tak, na której planecie powinny się spotkać, aby łączna liczba użyć statków była najmniejsza? Innymi słowy, czy istnieje planeta $c$, do której zwykły pasażer może dotrzeć zarówno z $a$, jak i z $b$, korzystając z pewnej liczby przelotów? Jeśli tak, która planeta $c$ minimalizuje sumę liczby użyć statków na drodze z $a$ do $c$ i na drodze z $b$ do $c$?

Jako znakomity programista zostałeś poproszony o znalezienie odpowiedzi na wszystkie ich pytania.

Zadanie

Napisz program odpowiadający na pytania, gdy harmonogram przyszłych zmian stanów statków i pytania podane są w kolejności chronologicznej.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczby całkowite $N,Q$, oddzielone spacją. $N$ to liczba planet, a $Q$ to łączna liczba zmian stanów i pytań.
• Kolejne $Q$ wierszy opisuje zmiany stanów i pytania w kolejności chronologicznej. $i$-ty z tych wierszy ($1 \le i \le Q$) zawiera dwie lub trzy liczby całkowite oddzielone spacjami. Oznaczmy pierwszą liczbę przez $T_i$. Zachodzi jeden z poniższych przypadków.

Gdy $T_i=1$

Wiersz zawiera liczby $T_i,A_i,B_i$ i oznacza, że statek zarządzany przez planetę $A_i$ zaczyna być używany do podróży na planetę $B_i$.

Zagwarantowano, że $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$, że statek planety $A_i$ jest w tym momencie nieużywany oraz że zwykły pasażer nie może w tym momencie dotrzeć z $B_i$ do $A_i$, korzystając z pewnej liczby przelotów statkami.

Gdy $T_i=2$

Wiersz zawiera liczby $T_i,A_i$ i oznacza, że statek zarządzany przez planetę $A_i$ przestaje być używany.

Zagwarantowano, że $1 \le A_i \le N$ oraz że statek planety $A_i$ jest w tym momencie używany.

Gdy $T_i=3$

Wiersz zawiera liczby $T_i,A_i,B_i$ i opisuje pytanie: jeśli w tym momencie jedna osoba jest na planecie $A_i$, a druga na planecie $B_i$, czy mogą spotkać się, podróżując statkami jako zwykli pasażerowie? Jeśli tak, na której planecie powinny się spotkać, aby liczba użyć statków była najmniejsza?

Zagwarantowano, że $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$.

Wyjście

Dla każdego pytania wypisz na standardowe wyjście:

• numer planety spotkania minimalizującej liczbę użyć statków, jeśli spotkanie jest możliwe;
• liczbę całkowitą -1, jeśli spotkanie jest niemożliwe.

Odpowiedzi wypisuj w kolejności pytań, po jednej w wierszu.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

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

Podzadania

Podzadanie 1 [10 punktów]

Spełnione są następujące warunki.

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

Podzadanie 2 [30 punktów]

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

Podzadanie 3 [60 punktów]

Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

-1
4

Uwagi

W tym przykładzie zmiany stanów i pytania przebiegają kolejno następująco:

• Statek zarządzany przez planetę $2$ zaczyna być używany do podróży na planetę $4$.
• W tym momencie osoby na planetach $2$ i $6$ nie mogą się spotkać, więc należy wypisać -1.
• Statek zarządzany przez planetę $4$ zaczyna być używany do podróży na planetę $3$.
• Statek zarządzany przez planetę $6$ zaczyna być używany do podróży na planetę $4$.
• W tym momencie osoby na planetach $2$ i $6$ mogą spotkać się na planecie $3$ lub $4$. Aby zminimalizować liczbę użyć statków, powinny spotkać się na planecie $4$, więc należy wypisać 4.

Wejście 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

Wyjście 2

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