В далёкой галактике есть $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 \le 1000000$.
• $1 \le Q \le 1000000$.

Подзадачи

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

Выполняются следующие условия.

• $N \le 5000$.
• $Q \le 5000$.

Подзадача 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