Как вы помните, Макс и другие студенты, находясь в командировке, часто пользуются услугами такси. На этот раз ребята отправились в другой соседний регион, где проводится знаменитый Апрельский Чемпионат.
Университет-организатор Апрельского Чемпионата имеет N корпусов, пронумерованных от 1 до N. Корпуса соединены сетью из M дорог, проезд по i-й из которых занимает Ti минут.
Макс и его друзья поселились в гостинице, находящейся в непосредственной близости от корпуса, имеющего номер S. К сожалению, никто из ребят не запомнил, в каком именно корпусе будет проходить чемпионат, поэтому сейчас они изучают карту города и планируют, как лучше всего добраться до того или иного корпуса.
Оказалось, что в городе, в котором проводится Апрельский Чемпионат, службы такси имеют ряд особенностей:
- Во-первых, этих служб очень много (можно считать, что сколь угодно большая группа пассажиров всегда сможет заказать такси).
- Во-вторых, несмотря на большое количество служб, в каждой из них можно заказать только одну машину.
- В-третьих, водители разных служб такси не очень жалуют друг друга, и поэтому обязательно поедут к месту назначения различными путями (пути A и B считаются различными, если существует хотя бы одна дорога, входящая в путь A и не входящая в путь B или наоборот).
Макс и другие студенты долго чесали в затылках, силясь понять бесконечную мудрость местной сферы транспортного обслуживания.
Сейчас ребята хотят выяснить, сколько существует корпусов, до которых они могут добраться одновременно и за минимально возможное время, если воспользуются местными службами такси и начнут поездку одновременно. Помогите им найти ответ на этот вопрос. Помните, что во всех такси 4 места для пассажиров.
Выходные данные
Выведите одно или более целых чисел — номера корпусов, до которых все студенты, стартовав одновременно, могут доехать также одновременно и за минимально возможное время. Номера следует выводить в порядке возрастания.