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

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

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

K. Корованы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Внимание: слово «корован» не содержит орфографических ошибок, так как является интернет-мемом (если не верите, можете после контеста посмотреть здесь: neolurk.org/wiki/Корованы). Однако во время сдачи ЕГЭ по русскому языку советуем всё же использовать вариант написания «караван».
Студент Илья часто прогуливает пары в университете. Друзья осуждают его за это, но они не знают, что всё освободившееся время Илья проводит не за просмотром сериалов или слушая музыку. Он делает компьютерную игру своей мечты! Действие игры происходит в лесу. Там есть эльфы, деревянные домики и злой. А ещё там можно грабить корованы... И хоть в данный момент в игре только один корован, у Ильи уже возникли трудности с реализацией процесса ограбления.
Игровой мир можно представить в виде нескольких поселений, соединённых дорогами. От любого поселения до любого другого можно добраться по дорогам (возможно, заходя в другие поселения по пути). Все поселения пронумерованы целыми числами от 1 до n. Все дороги двусторонние и имеют одинаковую длину, равную единице. Перемещаться вне дорог нельзя. Корован идёт из поселения s в поселение f по одному из кратчайших путей. Поселение r является логовом злого. Днём группа разбойников из поселения r получила задание ограбить корован. Вечером этого же дня они раздобудут точный план пути, по которому корован пойдёт на следующее утро. В течение ночи разбойники могут переместиться в любое поселение, которое будет посещено корованом, даже в поселения s и f, и, устроив там засаду, утром ограбить корован. Разумеется, среди всех таких поселений разбойники выберут ближайшее к поселению r. До вечера ещё далеко, и пока они не знают, по какому пути пойдёт корован, но хотят знать, какое максимальное расстояние им придётся преодолеть в худшем случае до поселения, в котором они смогут его ограбить. Помогите Илье посчитать это расстояние, и тогда, возможно, он снова начнёт ходить на пары!

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

В первой строке даны целые числа n и m (3 ≤ n ≤ 105; 2 ≤ m ≤ 105) — количество поселений в игровом мире и количество дорог между ними. В следующих m строках дано описание дорог. В каждой из них записаны целые числа a и b — номера поселений, между которыми есть дорога. Гарантируется, что любая дорога соединяет два различных поселения, а между любыми двумя поселениями проходит не более одной дороги. Также гарантируется, что сеть дорог является связной. В последней строке записаны целые числа s, f и r — номера поселений, описанных в условии. Гарантируется, что эти поселения попарно различны.

Результат

В единственной строке выведите искомое расстояние.

Пример

исходные данныерезультат
7 7
1 2
2 4
2 5
3 4
4 6
5 6
6 7
1 7 3
2

Замечания

В примере корован может пойти либо по пути 1-2-4-6-7, либо по пути 1-2-5-6-7. В первом случае разбойники устроят засаду в поселении 4, которое находится на расстоянии 1 от логова злого, во втором случае — в поселении 2 или в поселении 6, которые находятся на расстоянии 2 от логова злого. Второй вариант хуже для разбойников, поэтому его и нужно выдать в качестве ответа.
Автор задачи: Олег Меркурьев
Источник задачи: Уральская региональная командная олимпиада по программированию 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2034. Корованы