Односторонні дороги#7950
У країні Віа міста з'єднані дорогами, якими можна їздити в обидва боки. Це стало причиною численних аварій, оскільки смуги руху не розділені: водії часто дивляться у свої смартфони під час водіння, що призводить до зіткнень із зустрічним транспортом. Щоб вирішити цю проблему, політики Віа запропонували ідею створити дороги лише з одностороннім рухом, тобто змінити існуючі дороги так, щоб кожна з них використовувалася лише в одному з двох можливих напрямків. Вони називають це "односторонньою ідентифікацією".
Мери не хочуть, щоб до їхніх міст вело занадто багато доріг з одностороннім рухом, оскільки це може викликати затори всередині міста. Вони вимагають знайти таке найменше ціле число , щоб для кожного міста кількість доріг з одностороннім рухом, які ведуть до нього, не перевищувала .
Перший рядок містить кількість міст n~(1 \le n \le 500).
Другий рядок містить кількість двосторонніх доріг m~(0 \le m \le 2.5 \cdot 10^3).
Кожен з наступних рядків містить два цілі числа і b~(1 \le a, b \le n, a \ne b), що позначають дорогу між містами і .
Між двома містами існує не більше однієї дороги.
Виведіть мінімальне число .
Приклад 1
Приклад 2