Недавно Ирина поехала отдыхать в один из самых известных городов Берляндии — город Берлятов. В городе находится n достопримечательностей, пронумерованных от 1 до n, некоторые из которых соединены односторонними дорогами. Дороги в Берлятове устроены так, что циклических маршрутов между достопримечательностями не существует.
Изначально Ирина находится у достопримечательности 1, а конечный пункт её путешествия — достопримечательность n. Естественно, Ирина хочет посетить как можно больше достопримечательностей во время своего путешествия. Однако, время пребывания Ирины в Берлятове ограничено, и она может пробыть там не больше T единиц времени.
Помогите Ирине определить, какое наибольшее количество достопримечательностей она сможет посетить на своём пути от достопримечательности 1 до достопримечательности n за время, не превышающее T. Гарантируется, что существует хотя бы один маршрут от достопримечательности 1 до достопримечательности n, на прохождение которого Ирина потратит не более T единиц времени.
Выходные данные
В первой строке выведите единственное целое число k (2 ≤ k ≤ n) — максимальное количество достопримечательностей, которые Ирина сможет посетить во время своего путешествия от достопримечательности 1 к достопримечательности n за время, не превышающее T.
Во второй строке выведите k различных целых чисел — номера достопримечательностей, которые посетит Ирина на своем пути, в порядке их посещения.
Если ответов несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 13
1 2 5
2 3 7
2 4 8
|
3
1 2 4
|
|
2
|
6 6 7
1 2 2
1 3 3
3 6 3
2 4 2
4 6 2
6 5 1
|
4
1 2 4 6
|
|
3
|
5 5 6
1 3 3
3 5 3
1 2 2
2 4 3
4 5 2
|
3
1 3 5
|