Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Эх, дороги!.. (20 баллов)

Задачу добавил: alef

Успешно сдано решений: 65

Когда сумки были распределены, встал вопрос, как добраться до дома Пети и Кати. Общественный транспорт в предновогодний вечер на дорогах встречался уже не очень часто: некоторые маршруты уже перестали ходить. Известно, между какими остановочными пунктами имеется прямая связь (т.е. от одной остановки до другой можно доехать без пересадок). Нужно найти самый короткий маршрут от дома Димы до дома Пети и Кати.
Если оптимальных маршрутов несколько, выведите тот, который содержит меньшее количество пересадок.


Формат входного файла input.txt
Первая строка - целое число N, 2<=N<=20 - общее число остановочных пунктов
Вторая строка - два целых числа D и P (0<=D, P<= N; D <> P) через пробел: номера остановок - ближайшей к дому Димы и ближайшей к дому Пети и Кати соответственно.
Затем следуют N строк, причем строка № J+2 (1<=J<=N) содержит целые числа - номера остановок через пробел, непосредственно связанных с остановкой № J

Формат выходного файла output.txt
Последовательность целых чисел через пробел - номера остановок в том порядке, в котором их будут проезжать друзья по пути от дома Димы к дому Пети и Кати

Пример входного файла
2
1 2
2
1


Пример выходного файла
1 2

Сдать задачу

Задать вопрос жюри по этой задаче