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 is of length 12.

Input

The input consists of multiple consists of $1$ or more test cases. The first line contains $2$ integers: the number of train stops $s$ ($2 \leq s \leq 25$) and the number of route segments $r$ ($1 \leq r \leq 25$) The next $r$ lines contains the number of the $2$ train stops connected by each of the next $r$ train segments. Train stops are numbered from $1$ to $s-1$. The train stops have degrees of $3$ or less and the train segments are undirected. 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