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

Чемпионат Урала 2012

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

F. Путешествия во времени

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Открытие сверхсветовых нейтрино вызвало к жизни целую цепочку научных достижений. Сначала учёным удалось разогнать до сверхсветовых скоростей отдельные протоны и нейтроны, затем — целые атомы, а вскоре и небольшие объекты. Но самым удивительным эффектом стало то, что при попытке разогнать какой-нибудь предмет до сверхсветовой скорости вдоль замкнутой траектории тот просто отправлялся в прошлое. Причём схема такого ускорителя оказалась настолько проста, что даже обычная микроволновка после небольшой доработки смогла отправить неспелый банан на неделю назад, чтобы тот дозрел.
Хотя эксперименты по отправке объектов в прошлое и дали отличные результаты, они не всегда проходили гладко. Порой предмет, отправленный назад во времени, сталкивался со своей версией из прошлого. После одного такого столкновения образовалась чёрная дыра, которая, прежде чем схлопнуться, успела поглотить половину исследовательской лаборатории. Несмотря на подобные инциденты, учёные продолжали работы по стабильному перемещению всё больших объектов. Вскоре в массовое производство был запущен транспортный корабль «Валькирия-500». Сверхсветовое перемещение позволяло ему прилетать в точку назначения в любой момент времени, даже в предшествовавший моменту отлёта.
Разведка доложила, что на одну из отдалённых планет прибывает с визитом лидер повстанческого движения. Вам, как самому талантливому спецагенту, дан приказ уничтожить его прямо в момент прибытия, пока на него не набросилась жадная до сенсаций пресса. У вас есть график всех рейсов «Валькирий» в этом секторе Галактики и право воспользоваться любыми из них. Но помните, что, если вы дважды окажетесь на одной и той же планете в одно и то же время, вы рискуете столкнуться с самим собой. Поскольку подобная встреча наверняка окажется фатальной, её нельзя допускать, пока задание не выполнено.

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

В первой строке записаны целые числа n и m — общее количество планет в секторе и рейсов «Валькирий» между ними (1 ≤ n ≤ 105; 0 ≤ m ≤ 105). В следующих m строках описываются рейсы. Описание каждого рейса состоит из четырёх целых чисел: номеров планет вылета и прилёта, времени вылета и времени прилёта. В последней строке записаны четыре целых числа — номер планеты, где вы находитесь, номер планеты, на которую прилетает лидер повстанцев, текущее время и время, когда прилетает лидер повстанцев. Все времена — целые числа в пределах от 0 до 106. Планеты пронумерованы целыми числами от 1 до n.

Результат

Если маршрута не существует, выведите «Impossible». В противном случае в первой строке выведите число k. В следующей строке выведите k чисел — номера рейсов, которыми стоит воспользоваться, в порядке следования по маршруту. Если существует несколько способов вовремя добраться до пункта назначения, выведите любой из них. Рейсы пронумерованы целыми числами от 1 до m в том порядке, в котором они описаны во входных данных.

Пример

исходные данныерезультат
4 3
1 2 10 20
2 4 50 20
4 3 20 30
1 3 10 30
3
1 2 3
Автор задачи: Дмитрий Иванков
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1905. Путешествия во времени