「條條大路通羅馬。」是一句古老的名言，但若這個假設成立，那就不難發展出一套找出任兩個城市之間一條路徑的演算法。
當你要從city A到city B時，你可以先從A到Rome，再從Rome到B，但這AB間可能存在一條更短的路徑。
對於Rome道路系統可以用一個簡單的結構描述：
從Rome開始有很多延伸出去的路通往相鄰的城市，從這些城市又有更多的路通往更遠的城市，以此類推……因此我們可以將城市和Rome按「等級」歸類，即等級i的城市只和等級i+1和等級i-1的城市相鄰（Rome則相當於等級0）。
系統內將不會出現環之類的路徑，任一個等級i的城市只能和一個等級i-1的城市相鄰，但可以和零個或多個等級i+1的城市相鄰，因此當我們要從一個等級i的城市走到Rome可以順著等級i-1的城市走。
給定一連串的城市和道路，你的程式必須找出兩個城市之間的最短路徑（我們以拜訪的城市數量代替兩城市間的距離）。輸入的第一行為測試資料筆數，隨後接著空白的一列。
測資的第一行包含兩個以空白分隔的整數，第一個整數M表示系統中有幾條道路，第二個整數N表示你將要詢問兩個城市的最短路徑。
接下來的M行包含了一對由空白分隔的城市名稱，城市名稱包含一個或多個字母，第一個字母一定是大寫，任兩個城市名稱不會以相同字母開頭。
Rome這個名稱至少會在一組測資裡出現一次，而Rome被視為等級0的城市（等級最低的城市），該城市名稱間表示有一條道路相連，且保證第一個出現的城市的等級一定比第二個城市的等級低。沒有一個城市名稱對會重複出現兩次。
接下來的N行包含了兩個城市，且保證任兩個城市名稱一定在先前描述道路系統時出現過，則請輸出從第一個城市到第二個城市的最短路徑為何。
任兩組測試資料間由一個空白行分格。對於每對題目的詢問，請依序輸出位於該兩個城市最短路徑上的城市，輸出的城市名稱以第一個大寫字母作代表。
對於任兩組輸出間請輸出一個空白行。
1 7 3 Rome Turin Turin Venice Turin Genoa Rome Pisa Pisa Florence Venice Athens Turin Milan Turin Pisa Milan Florence Athens Genoa
TRP MTRPF AVTG
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||