Задачи командного чемпионата

Астронавту необходимо попасть как можно быстрее из одного отсека космической станции в другой. К несчастью в тот момент, когда он отправился в путь, из технологических ниш появились роботы и принялись за уборку коридоров станции. Роботы движутся в несколько раз медленнее человека. Астронавт может идти вслед за роботом с той же скоростью, но не может обойти его в коридоре, так как робот занимает всю ширину коридора. Отсеки достаточно большие, чтобы роботы и астронавт могли пройти мимо друг друга, но время на переход из одного коридора в другой считается равным 0. Если астронавт попадает в некоторый отсек одновременно с роботом, то астронавт не может обогнать робота и попасть в коридор, который робот будет убирать следующим, или успеть выйти из этого коридора. Каждый коридор станции убирается только одним из роботов ровно один раз.

Напишите программу, которая поможет астронавту найти минимальный по времени путь из отсека 1 в отсек `N` с учетом передвижений роботов.

Ввод содержит в первой строке три целых числа – количество отсеков `N` (`1\ <\ N\ ≤\ 1000`), количество роботов `M` (`1\ ≤\ M\ ≤\ N`) и отношение скорости астронавта к скорости робота `S` (`2\ ≤\ S\ ≤\ 10`). Далее следует `M` строк, каждая строка начинается с количества убираемых роботом коридоров `k_i`, далее следует номер начального отсека пути робота, далее следует `k_i` пар целых чисел – длина коридора (целое от 1 до 1000) и номер отсека, в который ведет очередной коридор на пути робота. Между двумя отсеками не более одного коридора, общее количество коридоров не превышает `10*N`. Из любого отсека можно попасть по коридорам в любой другой.

В первой строке вывести одно целое число `K` – количество коридоров в минимальном по времени пути из отсека 1 в отсек `N`. Во второй строке вывести `K+1` число – номера отсеков, по которым проходит минимальный путь. Если существует несколько вариантов решения, нужно вывести один (любой) из них.

3 1 10
3 3 1 1 4 2 5 3

2
1 2 3