Поселенці Катана
У грі 1995 року "Поселенці Катана" гравці намагаються домінувати на острові, будуючи дороги, поселення та міста в незвіданій пустелі.
Ви працюєте в компанії-розробнику програмного забезпечення, яка щойно вирішила створити комп'ютерну версію цієї гри, і вас обрали для реалізації одного з особливих правил гри:
Наприкінці гри гравець, який побудував найдовшу дорогу, отримує два додаткових переможних очка.
Проблема в тому, що гравці зазвичай будують складні дорожні мережі, а не лише один лінійний шлях. Отже, визначення найдовшої дороги не є тривіальною справою (хоча гравці зазвичай бачать це відразу).
Порівняно з оригінальною грою, тут ми розглянемо спрощене завдання: вам надається набір вершин (міст) і ребер (доріг) довжини 1, що з'єднують вершини. Найдовша дорога визначається як найдовший шлях у мережі, в якому не використовується ребро двічі. Однак вершини можна відвідувати більше одного разу.
Вхідні дані
Містить один або кілька тестів. Перша рядок кожного тесту містить два цілих числа: кількість вершин n (2 ≤ n ≤ 25) і кількість ребер m (1 ≤ m ≤ 25). Наступні m рядків описують m ребер. Кожне ребро задається номерами двох вершин, з'єднаних ним. Вершини пронумеровані від 0 до n - 1. Ребра неорієнтовані. Вершини мають ступінь три або менше. Мережа не обов'язково є зв'язною. Введення завершується двома 0 для n і m.
Вихідні дані
Для кожного тесту в окремому рядку виведіть довжину найдовшої дороги.
