Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мутанты-навигаторы - единственные, кто может прокладывать пути между планетами в неспокойном варпе, ориентируясь на свет маяка-Астрономикона. В галактике `N` планет, пронумерованных от 1 до `N`. Для каждого нового варп-перехода, разведанного навигатором, известен непрерывный отрезок номеров планет `[L_1; R_1]`, с орбиты которых можно войти в этот переход, и отрезок номеров планет `[L_2; R_2]`, на орбиту которых из перехода можно выйти (все границы - включающие). Все варп-пути в порядке их нахождения фиксируются в бортовом журнале. Время от времени навигатору требуется решать свою основную задачу: находить маршрут между заданной парой планет, пользуясь только известными к этому моменту переходами. Помогите навигатору в его работе.
В первой строке ввода содержатся два натуральных числа: `N` - число планет (`2<=N<=10^5`) и `Q` - число событий (`1<=Q<=10^5`). Затем следует `Q` строк - описания событий в хронологическом порядке. Каждое событие начинается с описания его типа: числа 1 или 2.
Число 1 означает нахождение нового перехода, соответствующая строка содержит еще 4 натуральных числа `L_1`, `R_1`, `L_2`, `R_2` (`1<=L_1<=R_1<=N, 1<=L_2<=R_2<=N`) - отрезки входа и выхода найденного перехода. Диапазоны могут пересекаться, все переходы являются односторонними. В начальный момент времени ни один переход не разведан.
Число 2 означает запрос на поиск маршрута, соответствующая строка содержит еще 2 различных натуральных числа, не превосходящих `N` - номера начальной и конечной планет. Гарантируется, что таких запросов в журнале будет не менее 1, но не более 50.
Для каждого запроса типа 2 выведите одно число: минимальное количество варп-переходов, по которым нужно пройти, чтобы добраться от начальной планеты до конечной. Пользоваться можно только теми маршрутами, которые уже разведаны на момент получения запроса. Если конечная планета не достижима, вывести -1.
```sample Пример ввода
100 7
1 10 20 80 90
1 75 85 50 100
2 13 99
2 90 91
1 100 100 1 99
1 1 49 5 15
2 33 34
```
```sample Пример вывода
2
-1
4
```
Пояснение: в первом случае, маршрут может выглядеть как 13->80->99. В третьем случае, маршрут может выглядеть как 33->10->80->100->34 (через переходы 4, 1, 2, 3 соответственно).
Начало
Рабочее место участника
Поиск в ширину (BFS)