ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Таблички с номерами маршрутов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Каждый, кто ездил на автобусе в Екатеринбурге, мог заметить, что на обратной стороне таблички с номером маршрута написан номер другого маршрута.
Однажды водитель нового автобуса пришел на склад и обнаружил, что там нет таблички с номером маршрута, по которому он должен был ехать. Кладовщик просто выдал ему случайную табличку и посоветовал поменять ее на табличку из другого автобуса. Любой водитель согласится обменять свою табличку на другую в том случае, если на ней указан номер его маршрута. Помогите новому водителю найти кратчайшую последовательность обменов, которая позволит ему получить табличку с номером его маршрута.

Исходные данные

Первая строка содержит целое число K – количество действующих автобусов, исключая новый автобус (1 ≤ K ≤ 1000). Следующие K строк содержат номер маршрута соответствующего автобуса и номер на обратной стороне его таблички. Номера маршрутов – это целые числа от 1 до 2000.
Последняя строка содержит целые числа T, S1 и S2 – номер маршрута нового автобуса и номера на табличке, выданной кладовщиком (1 ≤ T, S1, S2 ≤ 2000; TS1; TS2).

Результат

Если невозможно получить нужный номер последовательностью обменов, выведите «IMPOSSIBLE». Иначе в первой строке выведите наименьшее необходимое количество обменов M > 0, а далее M строк, содержащих номера автобусов (не маршрутов!) с водителями, чьи таблички последовательно должны быть заменены. Автобусы пронумерованы от 1 до K в том порядке, в котором они описаны во входных данных. Если есть несколько оптимальных решений, вы можете вывести любое.

Пример

исходные данныерезультат
4
8 5
5 4
7 4
1 5
4 1 8
2
4
2
Автор задачи: Станислав Васильев
Источник задачи: USU Open Collegiate Programming Contest March'2001 Senior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1096. Таблички с номерами маршрутов