В волшебном королевстве Эльдория две странствующие башни, Лиана и Тарин, стартуют из разных городов. Их задача — добраться до одной и той же точки на карте королевства, чтобы вместе разгадать древнюю загадку королевства. Все дороги между городами этого королевстсва одинаковы по длине, но не между всеми городами они существуют. Если дорога существует, то время ее прохождения одинаково для каждой из башен.
Ваша задача — определить оптимальное место встречи так, чтобы минимизировать время ожидания встречи.
Входные данные:
- Первая строка содержит два целых числа 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 — минимальное время встречи, т.е. минимально возможное время, когда обе странствующие башни окажутся в одном городе (под временем понимается максимальное количество дорог, которое пройдет одна из башен)
- Во второй строке выведите номер города
к, в котором башни встретятся. Если таких городов несколько, вывести минимальный номер
- Если точки встречи не существует, вывести
-1
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3
1 2
3 4
|
-1
|
|
2
|
5 4
2 5
1 2
2 3
3 4
4 5
|
2
3
|