В игре года 1995 года в "Поселенцах Катана" игроки пытаются доминировать на острове строя дороги, поселения и города в неизведанной пустыне.

Вы работаете в компании - разработчике программного обеспечения, которая только что решила разработать компьютерную версию в этой игре, и Вы выбраны для реализации одного из особых правил игры:

По окончании игры игрок, построивший самую длинную дорогу, получает два дополнительных победных очка.

Проблема в том, что игроки обычно строят сложные дорожные сети, а не только один линейный путь. Следовательно, определение самой длинной дороги не является тривиальным делом (хотя игроки люди обычно видят это сразу).

По сравнению с оригинальной игрой, здесь мы рассмотрим упрощенную задачу: Вам предоставляется набор вершин (городов) и ребер (дорог) длины 1, соединяющих вершины. Самая длинная дорога определяется как самый длинный путь в сети, в котором не используется ребро дважды. Однако вершины можно посещать более одного раза.

Входные данные

Содержит один или несколько тестов. Первая строка каждого теста содержит два целых числа: количество вершин n (2 ≤ n ≤ 25) и количество ребер m (1 ≤ m ≤ 25). Следующие m строк описывают m рёбер. Каждое ребро задается номерами двух вершин, соединенных им. Вершины пронумерованы от 0 до n - 1. Ребра неориентированные. Вершины имеют степень три или меньше. Сеть не обязательно является связной. Ввод завершается двумя 0 для n и m.

Выходные данные

Для каждого теста в отдельной строке выведите длину самой длинной дороги.