ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2012

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Машина инженера Ивана

Ограничение времени: 1.5 секунды
Ограничение памяти: 64 МБ
Мир в опасности. Ужасные землетрясения гремят по всей планете. Рушатся дома, реки выходят из берегов, становится почти невозможно попасть из одного города в другой. Даже там, где сохранились хоть какие-то дороги, ездить сложно, потому что из-за движений почвы они стали слишком крутыми.
К счастью, у инженера Ивана есть машина, которая отлично умеет ездить как в горку, так и с неё. Правда, за движение вверх и вниз отвечают разные передачи, так что во время езды всё время приходится их переключать. Ещё у инженера Ивана есть хороший друг — геолог Орлов, вместе с которым Иван может изобрести способ спасения мира от землетрясений. Да вот незадача — друг-геолог живёт в другом городе.
Ивану очень хочется спасти мир, но у его машины начала изнашиваться коробка передач. Помогите Ивану спасти мир, а для этого найдите такой путь до города, в котором живёт Орлов, чтобы движение по этому пути требовало как можно меньшего количества переключений передачи. В начале своего пути Иван может включить любую из передач, и эту операцию не нужно учитывать при подсчёте количества переключений.

Исходные данные

В первой строке даны целые положительные числа n и m — число городов и дорог между ними (2 ≤ n ≤ 10 000; 1 ≤ m ≤ 100 000). В следующих m строках записано по два различных целых числа в пределах от 1 до n — номера городов, которые соединяет очередная дорога. Причём первым всегда указан город, находящийся ниже, то есть тот, из которого по этой дороге нужно ехать в гору. По всем дорогам можно двигаться в обоих направлениях. Между любыми двумя городами существует не больше одной дороги. В последней строке даны номера двух различных городов — тех, в которых живут Иван и геолог Орлов, соответственно. Хотя большинство дорог и были разрушены, Иван точно знает, что путь до геолога Орлова всё ещё существует.

Результат

Выведите одно число — минимальное количество переключений передачи для того, чтобы добраться в город Орлова.

Примеры

исходные данныерезультат
3 2
1 2
3 2
1 3
1
3 3
1 2
2 3
3 1
1 3
0
Автор задачи: Григорий Назаров (подготовка — Булат Зайнуллин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2012
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1930. Машина инженера Ивана