В глобальной сети, виртуальной Матрице, две программы-хакеры — Рей и Зета — начинают работу из разных узлов сети. Их цель — найти одну общую точку встречи (сервер), чтобы объединить данные и завершить миссию. Передача данных между серверами происходит за 1 условную единицу времени, но, к сoжалению, не между всеми серверами есть сети, по которым программы-хакеры могут перемещаться. Та из программ-хакеров, которая доберется до сервера, где они встречаются, первой, будет ждать другую. Ваша задача — определить оптимальное место встречи (сервер) так, чтобы минимизировать время ожидания.
Входные данные:
- Первая строка содержит два целых числа n и m (1 ≤ n ≤ 20000, 0 ≤ m ≤ 40000) — число серверов и виртуальных связей между ними соответственно. Серверы пронумерованы от 1 до n.
- Вторая строка содержит два целых числа s1 и s2 (1 ≤ s1, s2 ≤ n, s1 ≠ s2) — начальные серверы Рея и Зеты.
- Далее следует m строк, каждая из которых содержит два целых числа u и v (1 ≤ u, v ≤ n), обозначающие возможность виртуального обмена между серверами u и v.
Выходные данные:
- Если существует точка встречи:
- В первой строке выведите целое число
t — минимальное время встречи, т.е. минимально возможное время, когда Рей и Зета окажутся на одном серверое (под временем понимается максимальное количество виртуальных переходов между серверами, которое совершит одна из программ)
- Во второй строке выведите номер сервера
к, в котором программы встретятся. Если таких серверов несколько, вывести минимальный номер
- Если точки встречи не существует, вывести
NO
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3
1 2
3 4
|
NO
|
|
2
|
3 3
1 2
1 2
3 1
2 3
|
1
1
|