821 - Page Hopping

最新的報導指出，平均而言只需19次點擊即可從任一網頁連結到www上的任何其他網頁，也就是說，如果把每一個網頁視為圖論中的一個節點，則任兩個節點的平均路徑長度為19。

給定一張圖，可由該圖中任一啟始節點拜訪其他所有節點，你的工作是要從中找出任兩個節點的平均最短路徑長度，以下圖為例，各節點間以有向邊所連接，這表示由 a 節點連到 b 節點的邊，並不表示 b 節點連得到 a 節點。

上圖中由節點1連接到節點2, 3, 4的最短長度分別為1, 1, 2；由節點2連接到節點1, 3, 4的最短長度分別為3, 2, 3；節點3連到節點1, 2, 4的最短長度為1, 2, 3；節點4連到節點1, 2, 3的最短長度為2, 3, 1。這些長度的總和為：1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22，由於共有12種可能的組合，故平均長度為22/12 = 1.833(精確到小數點後三位)。

Input 

輸入會有多組測試資料，每組測試資料會有任意多組整數對 a 與 b，每組整數對表示編號 a 網頁連接到編號 b 網頁，所有網頁編號皆在1 ~ 100的範圍間，每組測試資料以一對零表示資料結束，並且在最後一組資料後會有一對零表示所有測試資料結束。所有網頁皆不會有連結到自已的情況，且每一節點致少會有一條路徑可以連結到其他節點。

Output 

請針對每組測試資料輸出任兩節點間的平均最短路徑長度，請輸出到小數點後三位，請參考範例資料格式。

Sample Input	Output for the Sample Input
1 2 2 4 1 3 3 1 4 3 0 0 1 2 1 4 4 2 2 7 7 1 0 0 0 0	Case 1: average length between pages = 1.833 clicks Case 2: average length between pages = 1.750 clicks

---

原文出處