В стране Виа города соединены дорогами, по которым можно ездить в обе стороны. Однако это стало причиной многих аварий, поскольку полосы движения не разделены: водители часто смотрят в свои смартфоны во время вождения, что приводит к столкновению со встречным транспортом. Чтобы облегчить эту проблему, политики Виа придумали великолепную идею создать дороги только с односторонним движением, то есть существующие дороги изменить так, чтобы каждую можно было использовать только в одном из двух возможных направлений. Они называют это "односторонней идентификацией".
Мэры не хотят, чтобы к их городам вело слишком много дорог с односторонним движением, поскольку это может вызвать пробки внутри города. Они требуют, чтобы было найдено такое наименьшее целое число , что для каждого города число дорог с односторонним движением, ведущих к нему, не превосходило бы .
Первая строка содержит количество городов от до .
Вторая строка содержит количество двусторонних дорог .
В каждой из следующих строк записаны два целых числа и , обозначающих дорогу между городами и .
Между двумя городами существует не более одной дороги.
Выведите минимальное число .