Извилистый путь (или кривая дорожка)
Задачу добавил: alef
Успешно сдано решений: 7
Наконец, Агент 008 смог пройти в здание компании и попытался проникнуть
в самую секретную комнату, где самые секретные программисты разрабатывали
самые секретные коды операционной системы. Надо сказать, что в здании
компании вообще нет коридоров. Некоторые комнаты соединены между собой
проходами, и бывает не так то просто попасть из одной в другую.
Кроме того, по комнатам и проходам постоянно прогуливаются сотрудники
службы безопасности компании.
Впрочем, для Агента 008 не существует препятствий. К тому же у него есть план,
на котором обозначены все проходы между комнатами. Поэтому ему удалось довольно
быстро добраться до самой секретной комнаты и миновать всех сотрудников службы
безопасности. Но в последний момент он утратил бдительность, и, как только он
вошел в самую секретную комнату, его остановил сотрудник службы безопасности.
Пришлось Агенту 008 сделать вид, что он направлялся совсем в другую комнату,
и ускорить шаг...
Он принял решение уходить как можно более длинным и запутанным маршрутом.
Составьте такой - самый длинный - маршрут для Агента 008.
Учтите, что в каждую комнату он должен заходить не более одного раза,
а в конечном итоге - выйти из здания.
Формат входного файла input.txt
Первая строка - два целых числа R (1<=R<=100) и S (1<=S<=R).
R - количество комнат в здании, S - номер секретной комнаты
Следующие R строк содержат информацию о соединенных комнатах.
Строка №J содержит список комнат, в которые можно попасть непосредственно
из комнаты №J-1 (J = 2, 3, ..., R+1). Если из комнаты имеется выход из здания,
то в списке присутствует 0.
Формат выходного файла output.txt
Целые числа - номера комнат, через которые Агент 008 прошел к выходу, следуя
самым длинным из возможных путей.
Пример входного файла
5 4
2 3 4 0
3 4 5
1
1
0 2 3
Пример выходного файла
4 1 2 5 0