喺遙遠宇宙嘅某個銀河入面，有 $N$ 個文明發達嘅星球，編號由 $1$ 到 $N$。每個星球都管理住一艘太空船。每艘太空船要唔係正用嚟前往另一個星球，要唔係處於停用狀態。假設星球 $a$ 管理嘅太空船正用嚟前往星球 $b$，噉艘太空船就會喺星球 $a$ 同星球 $b$ 之間來回多次。太空船由星球 $a$ 飛去星球 $b$ 嗰陣，普通乘客可以搭船由星球 $a$ 去星球 $b$；但由星球 $b$ 返回星球 $a$ 嗰陣，由於燃料問題或者需要運貨等原因，普通乘客唔可以上船。另外，如果星球 $a$ 管理嘅太空船處於停用狀態，佢就會喺星球 $a$ 待命。

而家所有太空船都處於停用狀態，之後各艘太空船嘅狀態變更時間表已經定好。每次狀態變更都係以下其中一種。

• 將星球 $a$ 管理、原本停用嘅太空船改為用嚟前往星球 $b$。不過，只有喺普通乘客無法透過搭太空船若干次，由星球 $b$ 去到星球 $a$ 嗰陣，先會進行呢種變更。
• 將星球 $a$ 管理、原本使用中嘅太空船改為停用。

有兩個人計劃去呢個銀河旅行。為咗安排會合，佢哋準備咗幾條以下形式嘅問題。

• 假設喺時間表中某個時刻，一個人喺星球 $a$，另一個人喺星球 $b$，兩個人可唔可以以普通乘客身份搭太空船會合？如果可以，喺邊個星球會合先可以令搭太空船嘅次數最少？亦即係話，有冇一個星球 $c$，令普通乘客可以搭太空船若干次，由星球 $a$ 同星球 $b$ 都去到星球 $c$？如果有，邊個星球 $c$ 可以令由星球 $a$ 去星球 $c$ 嘅搭船次數，加上由星球 $b$ 去星球 $c$ 嘅搭船次數，總和最細？

身為優秀程式員嘅你，獲邀求出佢哋所有問題嘅答案。

任務

畀定按時間先後排列嘅太空船狀態變更時間表同問題，請寫一個程式回答所有問題。

輸入格式

由標準輸入讀入以下資料。

• 第一行有兩個用空格分隔嘅整數 $N,Q$，表示有 $N$ 個星球，而狀態變更次數同問題數目加埋係 $Q$。
• 之後 $Q$ 行按時間先後表示狀態變更同問題。當中第 $i$ 行（$1 \le i \le Q$）有兩個或者三個用空格分隔嘅整數。設第一個整數係 $T_i$，情況係以下其中一種。

(i) $T_i=1$

呢行有整數 $T_i,A_i,B_i$，表示以下狀態變更：將星球 $A_i$ 管理嘅太空船改為用嚟前往星球 $B_i$。

保證 $1 \le A_i \le N$、$1 \le B_i \le N$、$A_i \ne B_i$；保證呢個時刻星球 $A_i$ 管理嘅太空船處於停用狀態；亦保證呢個時刻普通乘客無法搭太空船若干次，由星球 $B_i$ 去到星球 $A_i$。

(ii) $T_i=2$

呢行有整數 $T_i,A_i$，表示以下狀態變更：將星球 $A_i$ 管理嘅太空船改為停用。

保證 $1 \le A_i \le N$，而且呢個時刻星球 $A_i$ 管理嘅太空船處於使用中狀態。

(iii) $T_i=3$

呢行有整數 $T_i,A_i,B_i$，表示以下問題：假設呢個時刻，一個人喺星球 $A_i$，另一個人喺星球 $B_i$，兩個人可唔可以以普通乘客身份搭太空船會合？如果可以，喺邊個星球會合先可以令搭太空船嘅次數最少？

保證 $1 \le A_i \le N$、$1 \le B_i \le N$、$A_i \ne B_i$。

輸出格式

對每條問題，依次喺標準輸出用一行輸出：

• 如果可以會合，輸出令搭太空船次數最少嘅會合星球編號；
• 如果唔可以會合，輸出整數 $-1$。

資料範圍

所有輸入資料都符合以下條件。

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

子任務

子任務 1 [10 分]

符合以下條件。

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

子任務 2 [30 分]

• 滿足 $T_i \ne 2$（$1 \le i \le Q$）。

子任務 3 [60 分]

冇額外限制。

樣例

輸入格式 1

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

輸出格式 1

-1
4

說明

喺呢個樣例入面，狀態變更同問題依次如下。

• 星球 2 管理嘅太空船改為用嚟前往星球 4。
• 呢個時刻，如果兩個人分別喺星球 2 同星球 6，佢哋唔可以會合，所以輸出 $-1$。
• 星球 4 管理嘅太空船改為用嚟前往星球 3。
• 星球 6 管理嘅太空船改為用嚟前往星球 4。
• 呢個時刻，如果兩個人分別喺星球 2 同星球 6，佢哋可以喺星球 3 或者星球 4 會合。要令搭太空船次數最少，應該喺星球 4 會合，所以輸出 4。

輸入格式 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

輸出格式 2

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