I. Трамвай
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

В берляндском городе С*** есть трамвайное депо и всего один трамвай. В депо работают три человека: водитель трамвая, кондуктор и начальник депо. Раньше трамвай каждое утро выезжал из депо и ездил по круговому маршруту. При этом трамвай проходил маршрут ровно за c минут. Начальник депо контролировал движение трамвая, выходя на улицу через каждые c минут, когда трамвай проезжал мимо депо, и лишал водителя трамвая премии, если тот опаздывал хотя бы на секунду.

Так было в прежние времена. Впоследствии из федерального бюджета Берляндии были выделены средства на расширение сети трамвайных путей в городе С***, и, как иногда бывает, средства были использованы по назначению. Сеть трамвайных путей была перестроена, в результате чего превратилась в обширную и разветвленную систему. Возможно, прежний круговой маршрут был разрушен. В городе С*** n перекрестков и теперь m трамвайных путей, соединяющих пары перекрестков. Движение в Берляндии одностороннее, поэтому по каждому из путей трамвай может ехать в одном направлении. Между двумя перекрестками может проходить несколько трамвайных путей, с одним или разными направлениями движения. Каждый путь соединяет пару различных перекрестков и имеет такую длину, что трамвай проходит его ровно за 1 минуту. Для каждого перекрестка существует хотя бы один путь, по которому можно уехать с этого перекрестка.

Итак, трамвайные пути были построены, но почему-то никто не позаботился об увеличении количества трамваев в городе С***! Трамвай так и продолжал ездить в одиночестве, но теперь у водителя появилась прекрасная возможность избавиться от неусыпного контроля начальника депо. Ведь благодаря разветвленной сети он получил свободу в выборе маршрута! Теперь водитель, достигнув очередного перекрестка, может выбрать путь, по которому поедет, произвольным образом. При этом трамвай может уехать даже в такие районы города С***, откуда невозможно вернуться обратно в депо из-за однонаправленного движения. Водитель не боится этой трудности: ночью, когда город спит, можно незаметно вернуться в депо, двигаясь по путям в обратном направлении.

Горожане ликовали. Ведь некоторые из них ждали трамвая на своих улицах вот уже несколько лет. Однако поведение водителя привело в ярость начальника депо. Теперь он вынашивает коварный план установки видеонаблюдения за непокорным трамваем.

План заключается в следующем. Начальник депо хочет установить видеокамеры на некоторых перекрестках, выбрать промежуток времени t и через каждые t минут отвлекаться от любимой телепередачи, чтобы проверить местоположение трамвая по камерам. При этом начальник депо хочет, чтобы во все моменты времени, кратные t, и только в них трамвай оказывался на перекрестке под камерой наблюдения. На перекрестке, где находится депо, камера должна быть установлена обязательно, с целью предотвращения возможного теракта против начальника депо. Среди всех возможных планов начальник депо выбирает план с наибольшим значением t (уж очень не любит он отвлекаться от любимой телепередачи, но приходится). Если таких планов несколько, выбирается тот, для которого требуется как можно меньше камер наблюдения. Найдите такой план.

Входные данные

В первой строке содержатся целые числа n и m (2 ≤ n, m ≤ 105) — количество перекрестков и количество трамвайных путей в городе С*** соответственно. Следующие m строк содержат описания путей в формате «u v», где u — начальный перекресток пути, а v — его конечный перекресток. Перекрестки пронумерованы целыми числами от 1 до n, причем трамвайное депо находится на перекрестке с номером 1.

Выходные данные

В первой строке выведите значение t. В следующей строке выведите число k — необходимое количество камер наблюдения. В следующей строке через пробел выведите номера перекрестков, на которых следует установить камеры. Номера выводите в порядке возрастания.

Примеры
Входные данные
4 5
1 2
2 3
3 4
4 1
1 4
Выходные данные
2
2
1 3