UVA-539 - The Settlers of Catan

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！

題意概要

本題給定所有節點之間的拓墣 (Topology)，試問在該拓墣上的最長路徑為多長？

• 分析：本題為「深度優先搜尋 (DFS)」的應用。在每次往下找路徑時，可以使用一個陣列記錄該路徑已經走過 (注意：雙向都要註記已走過)，避免重覆走已經走過的路徑。

Input

The input file will contain one or more test cases. The first line of each test case contains two integers: the number of nodes $n$ ($2 \le n \le 25$) and the number of edges $m$ ($1 \le m \le 25$). The next $m$ lines describe the $m$ edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from $0$ to $n − 1$. Edges are undirected. Nodes have degrees of three or less. The network is not neccessarily connected. Input will be terminated by two values of $0$ for $n$ and $m$.

Output

For each test case, print the length of the longest road on a single line.

Sample Input

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

Sample Output

2
12