카탄의 개척자

1995년 '올해의 게임'으로 선정된 보드게임 카탄의 개척자에서, 플레이어들은 미지의 황무지에 길과 개척지, 도시를 건설하며 섬을 지배하려 경쟁합니다.

한 소프트웨어 회사가 이 게임의 컴퓨터 버전을 개발하고 있으며, 당신은 다음 특별 규칙 하나를 구현해야 합니다.

게임이 끝나면, 가장 긴 길을 건설한 플레이어가 추가 승점 2점을 얻는다.

플레이어들은 보통 하나의 직선 경로가 아니라 복잡한 도로망을 건설하므로, 가장 긴 길을 찾는 일은 (사람은 대개 한눈에 알아볼지라도) 간단하지 않습니다.

여기서는 단순화한 문제를 풉니다. 정점(도시)들의 집합과, 정점들을 잇는 길이가 각각 $1$인 간선(도로 구간)들의 집합이 주어집니다. 가장 긴 길이란 어느 간선도 두 번 사용하지 않으면서 네트워크를 지나는 가장 긴 경로입니다. 다만, 정점은 여러 번 방문해도 됩니다.

예를 들어, 다음 네트워크에는 길이가 $12$인 길이 있습니다.

o      o--o      o
 \    /    \    /
  o--o      o--o
 /    \    /    \
o      o--o      o--o
           \    /
            o--o

입력은 하나 이상의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 정점의 수 $n$ ($2 \le n \le 25$)과 간선의 수 $m$ ($1 \le m \le 25$), 두 정수가 주어집니다. 이어지는 $m$개의 줄에는 각 간선이 잇는 두 정점의 번호가 주어집니다. 정점은 $0$부터 $n-1$까지 번호가 매겨집니다. 간선은 방향이 없습니다. 모든 정점의 차수는 3 이하입니다. 네트워크가 반드시 연결되어 있지는 않습니다.

입력의 끝은 $n$과 $m$이 모두 $0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 가장 긴 길의 길이를 한 줄에 출력하세요.