Входной файл: PATH.IN Выходной файл: PATH.OUT Время на тест: 5 секунд Тесты к задаче:Скачать
Дана система односторонних дорог, определяемая набором пар городов. Каждая
такая пара (i,j) указывает, что из города i можно проехать в город j, но это
не значит, что можно проехать в обратном направлении.
Необходимо определить, можно ли проехать из заданного города А в заданный
город В таким образом, чтобы посетить город С и не проезжать ни по какой
дороге более одного раза.
Входные данные задаются в файле с именем PATH.IN следующим образом. В
первой строке находится натуральное N(N<=50) - количество городов (города
нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) -
количество дорог. Далее в каждой строке находится пара номеров городов,
которые связывает дорога. В последней (M+3)-й строке находятся номера городов
А, В и С.
Ответом является последовательность городов, начинающаяся городом А и
заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен
быть записан в файл PATH.OUT в виде последовательности номеров городов по
одному номеру в строке. Первая строка файла должна содержать количество
городов в последовательности. При отсутствии пути записать в первую строку
файла число -1.