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

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

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

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

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