在遙遠宇宙的某個銀河中，有 $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