539 - The Settlers of Catan

1995年推出的遊戲"卡坦島拓荒"(Settlers of Catan)曾榮獲德國年度遊戲大賞，玩家們必須在資源豐沛的荒島上拓荒，在未知的領域上開拓殖民地、建造道路與城市。你現在被雇用來設計該遊戲的電腦版本，並請你實作該遊戲的的一項特殊規則：路王

遊戲結束時，擁有最長道路的玩家為路王，並獲得額外的三分獎勵。

問題是每個玩家所建造的道路網路較為複雜，並非只是直線路段，所以決定最長路徑並非一項易事(但通常人眼可以直覺的分辨出來)。
不同於原始遊戲有制定許多額外的規則，例如當道路被對方玩家以城市截斷時，不計入總長度，在此我們不必考慮這些額外的規則，只需考慮最簡化的情況： 給定一些節點(城市)與連接節點且長度為1的邊(路段)，最長的路徑限定為網路內同一個邊只計算一次的路徑，但同個節點可拜訪超過一次。
例如下圖網路中，最長路徑長為12。

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

Input

輸入有多組測試資料。每組測試資料的第一列有兩個整數：n (2 <= n <= 25)表示節點數，m (1 <= m <= 25)表示邊數，接下來有 m 列，每列表示一個連接兩個節點的邊，節點的編號為0 ~ n-1，邊沒有方向性，一個節點最多連接三個邊，網路並非是連通的。
當 n = m = 0 表示測試資料結束。

Output

請針對每組測試資料輸出最長路徑長度。

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

---

原文出處