Problem G
Ticket to Ride

In the board game Ticket to Ride, the objective is to get the most possible points to win. One way to earn a large amount of points at the end of the game is by building the longest train route. This earns the player a helpful $10$ points.

Your job is to help implement a computer version of the game by determining the longest train path.

In a simplified version, you are given a set of train stops and a set of route segments of length $1$. The longest route must not use a route segment more than once. The train stops can be used more than once.

In this case, the longest route has length $12$.

Input

The input consists of at most $50$ test cases.

The first line of each test case contains the integers $s$ and $r$ ($2 \leq s \leq 25$, $1 \leq r \leq 25$), the number of train stops and route segments.

The next $r$ lines each contain the integers $u$, $v$ ($0 \leq u,v \leq s-1$, $u \neq v$), meaning that there is an undirected route segment between the stops numbered $u$ and $v$. Additionally, there is at most one route segment between every pair of train stops.

Every train stop has degree $3$ or less. The network may not necessarily be connected. The input is terminated with a line containing $2$ zeroes.

Output

For each test case, print the length of the longest route.

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

2
12