Weit draußen im Universum gibt es in einer Galaxie $N$ Sterne mit entwickelten Zivilisationen. Die Sterne sind von $1$ bis $N$ nummeriert. Jeder Stern verwaltet ein Raumschiff. Ein Raumschiff wird entweder für Flüge zu einem bestimmten anderen Stern eingesetzt oder ist außer Betrieb. Wird das von Stern $a$ verwaltete Raumschiff für Flüge zu Stern $b$ eingesetzt, fliegt es wiederholt zwischen $a$ und $b$ hin und her. Auf dem Flug von $a$ nach $b$ können gewöhnliche Reisende mitfliegen. Auf dem Rückflug von $b$ nach $a$ dürfen sie jedoch aus Gründen wie Treibstoffversorgung und Frachttransport nicht mitfliegen. Ist das von Stern $a$ verwaltete Raumschiff außer Betrieb, wartet es auf Stern $a$.

Anfangs sind alle Raumschiffe außer Betrieb. Der Zeitplan für künftige Zustandsänderungen steht bereits fest. Jede Änderung hat eine der folgenden Formen.

• Das bisher unbenutzte Raumschiff von Stern $a$ wird für Flüge zu Stern $b$ in Betrieb genommen. Dies geschieht jedoch nur, wenn gewöhnliche Reisende nicht durch mehrere Raumschiffflüge von $b$ nach $a$ gelangen können.
• Das bisher eingesetzte Raumschiff von Stern $a$ wird außer Betrieb genommen.

Zwei Personen, die eine Reise durch diese Galaxie planen, haben einige Anfragen der folgenden Art vorbereitet, um ihre Treffen zu planen.

• Wenn sich zu einem bestimmten Zeitpunkt im Zeitplan eine Person auf Stern $a$ und die andere auf Stern $b$ befindet, können sie als gewöhnliche Reisende mit Raumschiffen zu einem gemeinsamen Treffpunkt gelangen? Falls ja, auf welchem Stern können sie sich mit der geringsten Gesamtzahl an Raumschifffahrten treffen? Mit anderen Worten: Gibt es einen Stern $c$, den gewöhnliche Reisende sowohl von $a$ als auch von $b$ durch mehrere Raumschifffahrten erreichen können? Falls ja, welcher Stern $c$ minimiert die Summe der Anzahl der Raumschifffahrten von $a$ nach $c$ und von $b$ nach $c$?

Als ausgezeichneter Programmierer sollst du alle Anfragen der beiden beantworten.

Aufgabe

Schreibe ein Programm, das die Anfragen beantwortet, wenn der Zeitplan der künftigen Zustandsänderungen der Raumschiffe und die Anfragen in zeitlicher Reihenfolge gegeben sind.

Eingabe

Lies folgende Daten von der Standardeingabe.

• Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $N,Q$. Es gibt $N$ Sterne, und die Gesamtzahl der Zustandsänderungen und Anfragen ist $Q$.
• Die folgenden $Q$ Zeilen beschreiben die Zustandsänderungen und Anfragen in zeitlicher Reihenfolge. Die $i$-te dieser Zeilen ($1\le i\le Q$) enthält zwei oder drei durch Leerzeichen getrennte ganze Zahlen. Sei $T_i$ die erste Zahl. Es liegt einer der folgenden Fälle vor.

Fall (i): $T_i=1$

Die Zeile enthält $T_i,A_i,B_i$ und beschreibt folgende Zustandsänderung: Das von Stern $A_i$ verwaltete Raumschiff wird für Flüge zu Stern $B_i$ in Betrieb genommen.

Es ist garantiert, dass $1\le A_i\le N$, $1\le B_i\le N$ und $A_i\ne B_i$ gelten, dass das Raumschiff von Stern $A_i$ zu diesem Zeitpunkt außer Betrieb ist und dass gewöhnliche Reisende zu diesem Zeitpunkt nicht durch mehrere Raumschifffahrten von Stern $B_i$ nach Stern $A_i$ gelangen können.

Fall (ii): $T_i=2$

Die Zeile enthält $T_i,A_i$ und beschreibt folgende Zustandsänderung: Das von Stern $A_i$ verwaltete Raumschiff wird außer Betrieb genommen.

Es ist garantiert, dass $1\le A_i\le N$ gilt und dass das Raumschiff von Stern $A_i$ zu diesem Zeitpunkt in Betrieb ist.

Fall (iii): $T_i=3$

Die Zeile enthält $T_i,A_i,B_i$ und beschreibt folgende Anfrage: Wenn sich zu diesem Zeitpunkt eine Person auf Stern $A_i$ und die andere auf Stern $B_i$ befindet, können sie als gewöhnliche Reisende mit Raumschiffen zusammenkommen? Falls ja, auf welchem Stern können sie sich mit der geringsten Anzahl an Raumschifffahrten treffen?

Es ist garantiert, dass $1\le A_i\le N$, $1\le B_i\le N$ und $A_i\ne B_i$ gelten.

Ausgabe

Gib für jede Anfrage in der gegebenen Reihenfolge eine Zeile auf der Standardausgabe aus:

• Falls ein Treffen möglich ist, die Nummer des Sterns, auf dem sie sich mit der geringsten Anzahl an Raumschifffahrten treffen können.
• Falls kein Treffen möglich ist, die ganze Zahl $-1$.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

Es gelten folgende Bedingungen.

• $N\le5\,000$.
• $Q\le5\,000$.

Teilaufgabe 2 [30 Punkte]

• Es gilt $T_i\ne2$ ($1\le i\le Q$).

Teilaufgabe 3 [60 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

-1
4

Hinweis

In diesem Beispiel erfolgen die Zustandsänderungen und Anfragen in folgender Reihenfolge.

• Das von Stern $2$ verwaltete Raumschiff wird für Flüge zu Stern $4$ in Betrieb genommen.
• Befinden sich die beiden Personen zu diesem Zeitpunkt auf Stern $2$ und Stern $6$, können sie sich nicht treffen. Daher wird -1 ausgegeben.
• Das von Stern $4$ verwaltete Raumschiff wird für Flüge zu Stern $3$ in Betrieb genommen.
• Das von Stern $6$ verwaltete Raumschiff wird für Flüge zu Stern $4$ in Betrieb genommen.
• Befinden sich die beiden Personen nun auf Stern $2$ und Stern $6$, können sie sich auf Stern $3$ oder Stern $4$ treffen. Um die Anzahl der Raumschifffahrten zu minimieren, sollten sie sich auf Stern $4$ treffen. Daher wird 4 ausgegeben.

Eingabe 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

Ausgabe 2

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