29079번 - Осада Ла-Рошели 다국어

문제

Во время осады Ла-Рошели Д’Артаньян решил продумать каждую мелочь. Его интересует коммуникация крепости.

Д’Артаньяну известно, что пушки в Ла-Рошели расположены на двух этажах. При этом на каждом этаже есть $n$ комнат, в каждой из которых есть пушка, а также лестница на другой этаж. Каждая комната соединена дверными проемами с двумя соседними на этаже, таким образом что если все время двигаться в одном направлении, можно по кругу обойти весь этаж. Для удобства Д’Артаньян занумеровал комнаты по порядку таким образом, что комната 1ドル$ граничит с комнатами $n$ и 2ドル,ドル комната 2ドル$ --- с 1ドル$ и 3ドル,ドル и так далее. При этом комнаты, соединенные лестницей, имеют одинаковый номер.

Гугеноты используют связных для коммуникации между стрелками, которые перемещается между ними. Длиной пути связного при проходе между пушками Д’Артаньян считает количество дверных проемов (при переходе с одного этажа на другой дверных проемов нет), которое нужно пройти, чтобы попасть от одной пушки к другой. Связные идеально знают крепость и всегда ходят по кратчайшему из возможных маршрутов.

Д’Артаньян хочет предложить кардиналу обрушить некоторые лестницы, чтобы увеличить длину пути связных и ослабить гугенотов. Для того, чтобы убедится в том, что план действенный, Д’Артаньян хочет посчитать, какие будут длины путей связных при разных вариантах развития событий. Его интересуют только те маршруты связных, которые начинаются на одном этаже, а заканчиваются на другом.

Во времена мушкетеров не было компьютеров, зато вы сейчас можете попробовать решить эту задачу.

입력

В первой строке находится два натуральных числа $n,ドル $m$ (3ドル \le n \le 10^5,ドル 1ドル \le m \le 2 \cdot 10^5$) --- количество пушек на этаже и количество событий.

В каждой из следующих $m$ строк заданы события в хронологическом порядке, в следующем формате: сначала идет натуральное число $t$ (1ドル \le t \le 2$) --- тип запроса,

• если $t=1,ドル то далее следует одно натуральное число $x$ (1ドル \le x \le n$) --- номер лестницы, которая будет разрушена;
• если $t=2,ドル то далее следуют два натуральных числа $x,ドル $y$ (1ドル \le x, y \le n$) --- номера комнат, на разных этажах.

Гарантируется, что всегда будет хотя бы одна неразрушенная лестница.

출력

Для каждого запроса второго типа выведите длину кратчайшего пути между двумя комнатами.

제한

노트

В первом примере лестницы не разрушаются, поэтому связные могут всегда переходить на другой этаж в стартовой комнате.

Во втором примере перейти из 1ドル$-ой комнаты одного этажа в 3ドル$-ю комнату другого можно, например, перейдя на другой этаж в 6ドル$-ой комнате, лестница в которой будет цела. Аналогично можно добраться и из 1ドル$-ой комнаты в 1ドル$-ю.