Мер міста вирішив, що по місто почало розїзджати занадто багато маршруток, і із-за цього жителі перестали користуватись трамваями. Необхідно провести реорганізацію фірми, яка керує всіма маршрутними таксі у місті А у тому місті, якщо ви не знали, було \textbf{N} зупинок машруток, деякі з яких були з'єднані дорогою. Якщо дві зупинки з'єднані дорогою, то маршрутка може без додаткових зупинок доїхать як від першої зупинки до другої, так і від другої до першої. Також відомо, що ніяка пара зупинок не з'єднана двома і більше дорогами і ніяка дорога не з'єднує зупинку саму з собою. Маршрутка зупиняється на всіх зупинках на свому шляху. Після отримання наказу зменшити кількість маршрутів фірма вирішила залишити лише кільцеві маршрути, які містять не менше трьох різних зупинок, при слідуванні по яким маршрутка не проеїзджає через одну зупинку \textbf{2} рази. Крім того, довільна пара маршрутів відтепер повинна відрізнятись хоча б однією дорогою. Фірма не мала бажання здавати позиції у вигідному бізнесі, тому вирішила створити найбільшу кількість маршрутів, які задовольняють заданим двом вимогам. Маршрути були пронумеровані числами від \textbf{1} до \textbf{K} (\textbf{K} --- кількість маршрутів). По кожному маршруту їздив рівно один мікроавтобус. Друга задача, яка постала перед фірмою --- скласти розклад роботи контролерів. Розклад являє собою таблицю, стовбцями якої є маршрути, а рядками --- моменти часу, у які відбувається контроль. Якщо у клітинці \[\textbf{T}, \textbf{I}\] стоїть число \textbf{X}, це означає, что мікроавтобус, який слідує по маршруту номер \textbf{I}, зупиняється для контроля на зупинці номер \textbf{X} у момент часу \textbf{T}. Клітинка може бути і пуста. Відомо, що протягом дня кожна маршрутка повинна зупинятись на кожній зупинці для контролю рівно один раз, тобто у кожному стовбчику стільки непустих клітинок, скільки зупинок на маршруті. Крім того, у один і той же момент часу на одній зупинці не повинні перевірятись \textbf{2} маршрутки, і, звичайно, одна маршрутка не може у один момент часу знаходитись на двох різних зупинках. Потрібно знайти мінімально можливе число рядків у такій таблиці. \InputFile У першому рядку вхідних даних знаходяться цілі числа \textbf{N} і \textbf{M} --- кількість зупинок і доріг у місті відповідно. \textbf{3} ≤ \textbf{N} ≤ \textbf{14}. У наступних \textbf{M} рядках перераховані пари зупинок, які з'єднано черговою дорогою --- числа від \textbf{1} до \textbf{N}. \OutputFile Виведіть ціле число --- мінімальну кількість рядків у розкладі.