В городе будущего Иннополис еще во всю идет стройка, но уже сейчас построено n зданий. Крышу каждого здания можно представить как прямоугольник со сторонами, параллельными осям координат. Никакие здания не касаются и не пересекаются.
Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.
Инну можно представить как точку на плоскости. Она может перемещаться по крыше, не выходя за ее границы, но не может находиться на границе крыши. Также она умеет прыгать с крыши на крышу, но только в направлениях, параллельных осям координат. В целях безопасности Инна не может перепрыгивать здания, то есть в любой момент прыжка под ней не должно находиться здание.
Помогите Инне посчитать, какое минимальное количество раз она должна прыгнуть с одной крыши на другую, чтобы попасть на здание с номером n.
Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 10
5). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа x
i1, y
i1, x
i2 и y
i2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (x
i1 < x
i2; y
i1 < y
i2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 10
9
Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.
| Ввод |
Вывод |
4
0 0 3 2
1 6 4 8
1 3 4 5
7 7 10 9 |
3 |
3
0 0 3 2
1 3 4 5
7 7 10 9 |
-1 |