Задача H. Московский метрополитен ≡

Условие

Ровно 76 лет назад, 15 мая 1935 года, начал работу московский метрополитен. Первоначально он состоял из 13 станций.

Рассмотрим модель московского метрополитена, как набора из 13 станций, соединенных M туннелями. Никакой туннель не ведет из станции в нее же и никакая пара станций не может быть соединена более чем одним туннелем. Для каждого туннеля i известно t_i — время проезда по нему. Движение поездов в туннелях двустороннее.

Тов. Сидоров находится на станции с номером s. У него выдалось T свободных минут и он решил прокатиться по станциям метрополитена. При этом, он хочет потратить на все переезды ровно T минут и вернуться на станцию s.

Определите, возможно ли это. Если да, то найдите последовательность номеров станций, которые должен посетить тов. Сидоров. Первым и последним числом в последовательности должен быть номер s.

Временем переходов между станциями и ожидания поездов следует пренебречь.

Формат входного файла

Формат выходного файла

В первую строку выходного файла выведите слово "YES", если требуемый маршрут существует, и "NO" в противном случае. Если ответ существует, то в следующей строке выведите искомый маршрут. Если ответов несколько, выведите любой из них.

Ограничения

1 ≤ s, u_i, v_i ≤ 13;

1 ≤ T, t_i ≤ 1000;

Примеры тестов

4 6 1
1 2 1
2 3 2
3 4 3
4 1 4

YES
1 2 3 2 1