Далеко в космосі, в одній галактиці, є $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$ мінімізує суму кількостей польотів зі світу $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\le1\,000\,000$.
• $1\le Q\le1\,000\,000$.

Підзадачі

Підзадача 1 [10 балів]

Виконуються такі умови:

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

Підзадача 2 [30 балів]

• $T_i\ne2$ ($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