567 - Risk

有一種桌上型遊戲叫Risk，玩家們要彼此攻城略地征服全世界，遊戲桌上有一個世界地圖，地圖上有許多國家。遊戲進行中，玩家的軍隊會駐紮在某一個國家，該軍隊只能攻擊鄰近的國家，隨著遊戲的進行不斷侵略與擴張，軍隊能在已被征服的國家間自由地移動。

隨著遊戲的進行，玩家們若需要調度兵力由一處移到另一處，就必須將路途上所有國家一一征服，通常玩家都會優先選擇介於兩地之間的國家，這樣能使需要侵略的國家數目降到最低。給定一張地圖上20個國家的相對位置關係圖，你必須寫一個程式計算從一地到另一地最少需要征服幾個國家，你不需要列出侵略的順序，只需要計算侵略國家的總數即可，例如，若起點位置與終點位置相鄰，則你的程式要輸出1。

第一組測試資料的位置關係如下圖所示：

Input

輸入會有多組測試資料，每組測試資料一開始會有19列，分別表示與前19個國家相鄰的國家，例如第一列會列出與編號1的國家互為鄰國關係的所有國家。為了避免列出重覆的資料，所列出與國家 I 相鄰的國家 J 必定是 I < J，在第 I 列上(I小於20)會有一個整數X，表示該列接下來會有X個整數，每個整數必定大於 I 且不會超過20。一組測試資料的第20列會是一個整數N() ，表示接下來會有N對整數，每一對整數表示侵略國家的起點與終點位置。( )。

輸入檔案會有多組測試資料，你的程式必須持續讀入直到遇見EOF為止。所有給定的國家之間必定存在最少一條路徑。

Output

輸出的資料請參考Sample Output，其格式為"Test Set #T"，T表示測試資料的編號，請靠#字號對齊。

接下來的N列請輸出由起點到終點最少需征服的國家數目，其格式請參考Sample Output，第一、二個字元為起始國家，第七、八個字元為終點國家，兩國的最小移動距離請在第11個字元處靠左對齊。每組測試資料之後請輸出一列空行。

Sample Input

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

Sample Output

Test Set #1
 1 to 20: 7
 2 to  9: 5
19 to  5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
 1 to 20: 4
 8 to 20: 5
15 to 16: 2
11 to  4: 1
 7 to 13: 3
 2 to 16: 4

原文出處