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