1236 - Disjoint Paths

給一張圖，具有 N 個點和 N-1 條有權重的邊。找到最多 K 條不相交(點和邊皆不重複使用)的路徑，而所有被選上的邊權重總和最大。

如上如所示，兩個不同限制下，在相同的圖中會有不同的答案。

在不相交路徑最多 K 條時，當 K = 1，如左圖所示，答案最大為 13 (5+2+6)。

當 K = 2，如右圖所示，答案最大為 15 ((5+1)+(3+6))。

Input 

輸入第一行會有一個整數 T，表示接下來的測資組樹。

對於每組測資，第一行會有兩個整數 N, K (K <= N <= 60)。

接下來會有 N - 1 行，每行上會有三個整數 A, B, D，表示一條無向邊於 A 到 B 權重為 D。
(1 <= A, B <= N, |D| <= 10000)

Output 

對於每組測資，輸出最大總和。

Sample Input 

2 
6 1 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1
6 2 
1 2 5
3 2 2
3 4 6
6 3 3
2 5 1

Sample Output 

13 
15

1199 - Elevator Stopping Plan

在 ZSoft Corp 這家公司中，每名員工都相當地勤奮，但是電梯問題總是困擾他們。
因為這家公司只有一台電梯運作，使得在早上的時候，總是會花很多時間在等待電梯。

Hal 相當聰明，想要改善這種情況，目標要把電梯改為更有效率，但這並不是簡單的工作。

公司總共有 31 樓，電梯上升一樓消耗 4 秒，也就是說將會使用 (31 - 1) ×4 = 120 秒到達頂樓，如果電梯打算停留某一層時，將會額外消耗 10 秒時間停止。如果電梯每層都停，將會消耗 30×4 + 29×10 = 410 秒 (不考慮停留在 31 樓)。

員工們可以打算爬樓梯，不管是往上或往下爬一層，都是消耗 20 秒。如果從 1 樓爬到 31 樓，則消耗 30×20 = 600 秒。當然，只爬樓梯肯定不是最好的方式。因此一些員工會使用電梯到達某一層之後，再爬樓梯到達他們自己的辦公室。

經過一段時間精密的思考後，Hal 最後找到一個方法改善這種情況。首先，電梯會先問所有人要到達的樓層，將會設計停留哪一層的方案，最小化最後一個人到達的時間。

例如，電梯被要求停留在第 4, 5, 10 樓時，停留方案為
1. 先停留於第 4 樓，此時消耗 3×4 = 12 秒，並且停止 10 秒。
2. 之後直接抵達 10 樓，此時時間為 3×4 + 10 + 6×4 = 46 秒。

到抵達 4 樓人在 12 秒時可以到達，抵達 5 樓的人可以在 12 + 20 = 32 秒，而要抵達 10 樓的人將在 46 秒後到達。


寫程式計算最小化最後一個人抵達的時間，並且輸出停留方案。

Input 

輸入有多組測資。

每組測資的格式如下：

n f₁ f₂ ... f_n

將會有 n 個樓層被要求停留， f₁ f₂ ... f_n 表示為要求停止的樓層。
 (n <= 30, 2 <= f₁ < f₂ < ... < f_n <= 31)

Output 

對於每組測資，輸出一行最小的最後一個人抵達的時間。

第二行，先輸出停留樓層的個數，再分別輸出停留樓層的編號。

如果有多組輸出，任何一組都可以。

Sample Input 

3 4 5 10
1 2
0

Sample Output 

46
2 4 10
4
1 2

1148 - The mysterious X network

École 理工學院已經存在深根柢固的同儕網路。

當同學遇到任何困難時，他可以藉由這個網路尋求協助，也就是說，他想要在網路上找到另一個人尋求協助，他必須由中間人代為轉達。

特別注意：同儕關係都是對稱的，而且必然可以找到所有人。

寫一個程式計算最少的中間人個數。

Input

輸入第一行有一個整數，表示有多少測資組。

對於每組測資，第一行會有一個整數 N (1 <= N <= 10⁵)，同儕編號為 0 到 N-1。

接下來會有 N 行，每行前 2 個整數 c, n_c ( <= 100) 表示同儕編號，以及關係個數。

接下來會有 n_c 個整數緊接在後，表示 c 的同儕。

最後一行會有兩個整數 c₁ 和 c₂ ，表示 c₁向 c₂ 求助。

Output

對於每組測資，分別輸出  c₁, c₂, 和最少中間人個數。

Sample Input 

1

4
0 3 1 2 3
1 1 0
2 2 0 3
3 2 0 2
1 2

Sample Output 

1 2 1

388 - Galactic Import

隨著新系統的引進，星系之間的出口進口貿易變得更加容易，HyperCommodities 打算進口物品從不同的星系，每個星系中的行星的原物料都有不同的價值。

• 每個星系中最多有 26 個星球，每個星球編號從 'A' 到 'Z'。
• 每個星球都可以進口和出口，而且都有不同的原物料。
• 其中會存在兩個星球間有貿易路線，每當原物料由其他星球轉口出去，每轉一次原物料價值將會折損當下的 5%。
• 至少存在一個星球會向地球開放貿易。

找到其中一個星球的原物料進口到地球具有最高價值。

Input

輸入有多組測資。

每組測資第一行會有一個整數 N 表示描述星球間的關係。

每一行的格式如下：

1. 星球的英文字母代號
2. 空白
3. 原物料的價值 d.dd
4. 空白
5. 一組字串，表示可以出口到的地方。以 '*' 表示地球。

Output

對於每組測資，輸出 ``Import from P''，P 為最高價值的星球代號。如果有多個，則選擇字典順序最小的。

Sample Input

1
F 0.81 *
5
E 0.01 *A
D 0.01 A*
C 0.01 *A
A 1.00 EDCB
B 0.01 A*
10
S 2.23 Q*
A 9.76 C
K 5.88 MI
E 7.54 GC
M 5.01 OK
G 7.43 IE
I 6.09 KG
C 8.42 EA
O 4.55 QM
Q 3.21 SO

Sample Output

Import from F
Import from A
Import from A

11487 - Gathering Food

冬天來臨，天氣越來越冷，許多動物採取不同的方法來適應冬天。

- 遷徙，移動到溫暖的地方。

- 很少有動物仍在冬天保持活躍。

- 冬眠，動物藉由深沉睡眠，降低體溫、心跳速度，而在秋天時準備足夠的食物以及體內脂肪。

而這題著重於第三點的例子，觀察一種特別的熊。


這種熊在一個特別的森林，將這個森林定義為 N x N 的網狀格子，每個格子只會有下列三種資訊。


'.' 空地
'#' 障礙物
[A-Z] 英文字母

森林中至少存在一個英文字母，所有字母只會存在唯一一個，如果存在有 n 個字母，這必然只會存在前 n 個字母，即當 n = 3 時，確切只會有 1 A, 1 B, 1 C。

這些字母表示當地區的食物，熊會從 'A' 開始搜集其他食物，每次只會往四個方向(上下左右)移動，由於特別的習性，會根據字母順序搜集食物，當熊到達食物所在地時，才能將食物收集起來。

計算熊收集食物的最少移動步數，以及在最少移動步數下，有多少移動方法。


// 翻譯備註，非要撿起的食物必須當做障礙物。

Input

有多組測資，每組第一行有一個整數 N (N <= 10)。

Output

對於每組測資，輸出測資組編號，如果無法搜集到所有食物，則輸出 ‘Impossible’。

反之分別輸出最短路徑長及路徑個數，輸出 mod 20437 後的結果即可。

Sample Input                             Output for Sample Input

5 A.... ####. ..B.. .#### C.DE. 2 A. .B 2 A# #B 0

Case 1: 15 1 Case 2: 2 2 Case 3: Impossible

11655 - Waterland

西元 3110 年，大多數的陸地已經陷入水中，只剩下少數的島嶼。水島是由許多小島嶼所組成，所有小島嶼間藉由隧道連接，每個隧道兩端確切只有 2 個島嶼。

水島總統想要去 Yablonoi 島度假，精英安全部隊必須要護送總統從 Kurai 島到 Yablonoi 島，他們必須選擇安全的隧道來前進。在每種可能路徑中，每條隧道都只能經過一次。

安全部隊每次派出有很多小隊一起出發，嘗試每種不同的路徑，每經過島嶼時，會留下一個小隊駐守，每次都只會剩下一個小隊抵達 Yablonoi 島，而一座小島可能會有多個小隊來自於不同次出發的。

現在安全部隊的負責人要計算總共派發出的小隊個數，並且計算有多少個小隊抵達目的地。

Input

測資第一行有一個整數 N (N < 40)，表示測資組數。

對於每組測資，第一行會有兩個整數 L, T (2 <= L <= 5000, 0 <= T <= 5*L)，分別表示島嶼個數，以及安全隧道的個數。

接下來會有 T 行，每行上有兩個整數 x, y (1 <= x, y <= L)，表示有一條有向隧道從 x 到 y。對於任兩個島嶼間最多有一條隧道連接，而島嶼編號 1 為 Kurai 島，島與編號 L 為 Yablonoi 島。

Output

對於每組測資，輸出測資組編號，以及兩個整數 S, D，分別表示總共需要的小隊數，以及最後抵達目的地的小隊總數。

只需打印出 mod 100000 的結果即可。

Sample Input                              Output for Sample Input

3 2 1 1 2 4 4 1 2 1 3 2 4 3 4 4 3 1 2 2 3 3 4

Case 1: 1 1 Case 2: 4 2 Case 3: 3 1

986 - How Many

在一個平面上的格子點中，考慮每次步驟為加上 (1,1) 或 (1,-1)，並且不會低於 x 軸，而每個山頂高 k 定義為在 (1,1) 步驟後 y=k 且緊接著 (1,-1) 步驟。

如下圖所示，左圖有 4 個山頂，其中 2 個山頂高度 2，另 2 個山頂高度 3。

右圖則有 3 個山頂，高度分別為 1, 2, 3。

Problem

從 (0, 0) 出發，中止於 (2n, 0)，並且確切存在 r 個山頂高度 k。

Input

輸入有多組測資。

每組一行有 3 個整數 n, r, k。
(1 <= n < 20, 0 <= r < 20, 1 <= k < 20)

Output

對於每組測資輸出一行，一個整數表示有多少種路徑走法， 答案小於 2³¹。

Sample Input

3 1 2
10 3 2

Sample Output

2
2002

10350 - Liftless EME

EME 建築在 2002 年到 2020 年間越建越高，但是電梯數量仍維持定量。因此這對於學生到教室是個很重要的問題，對於 ACM 練習賽的選手特別重要，比賽從每個星期二的 2:00 pm 開始，此時電梯和樓梯都擠滿了實驗室的學生。

所有參賽選手打算抄捷徑到 ACM 教室，他們偷偷地在每一層天花板挖洞，並且每個洞向下放置一個樓梯，因此他們可以藉由這些到達另一個樓層，藉以避面大批人群。

問題為：現在有很多捷徑，計算一個最短路徑抵達目的地。

目標從地面 (0 層)  到達頂樓 (n-1 層)，特別注意參賽者只會往上爬。

Input

輸入有多組測資。

對於每組測資，第一行會有一個測資組名稱，長度不超過 12 字元。

接著會有 2 個整數 n, m，分別表示 EME 建築的樓層數量、每一層有的洞數量。

接下來會有 m(n-1) 行，每行上會有 m 個整數，在第 k*m+i 行上，表示在第 k 層的第 i 個洞的資訊，該行的第 j 個整數表示到第 k+1 層的第 j 個洞的時間。

(0 <= k < n-1 < 120, 1 < i, j < m <= 15)

Output

對於每組測資輸出兩行，第一行為測資組名稱，第二行為最少時間從地面到頂樓。

Sample Input

Sample001

3 2

1 2

3 4

5 6

7 8

Sample Output

Sample001

10

1198 - The Geodetic Set Problem

G = (V, E) 表示一連通圖，不存在 loops(自己連自己) 和重覆的邊，V, E 分別表示節點與邊。

對於 u, v ∈ V 必然會存在一條最短路徑，而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合，而 S ⊆ V，

如果 I(D) = V，則這節點集合 D 被稱作為 G 的其中一個 geodetic set， The geodetic set problem 就是要檢驗 D 是否為 geodetic set。

以上圖為例，I(2, 5) = {2, 3, 4, 5}，即所有可能在最短路徑上的所有點，然而
I(2, 5) 並不是一個 geodetic set，因為並不等於 {1, 2, 3, 4, 5}。

假如 D = {1, 2, 5}，則 I(D) = V，同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set，但
{3, 4, 5} 卻不是，因為節點 1 並不在 I(D) 中。


Input

輸入有多組測資，每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。

接下來會有 n 行，在第 i 行(1 <= i <= n)上會有數個整數，表示與節點編號 i 相連的點。

接著會有一行一個整數 q，表示接下有多少組詢問。
 
每組詢問一行，行上的每個整數 D 集合內的節點編號。
Output

對於每組詢問的 D，判斷 D 是否為 geodetic set。

Sample Input

5
2 3
1 3 4
1 2 5
2 5
3 4
6
1 2 3 4 5
1 2 5
2 4
1 3 4
1 4 5
3 4 5
 
Sample Output

yes
yes
no
yes
yes
no

925 - No more prerequisites, please!

最近，我正在準備給予少部分學生的畢業課程指導，向同事要課程之間的關係，而有部分課程需要先修課程，定義這先修課程的集合為 c，也就是說學生必須先修過 c 的所有課程，才能修這門課。

不過同事太熱心了，給了過多的資訊，過多是什麼意思，接下來我會解釋 ...：

• 假設有課程名為 ca, cb, cc, cd, cd
• 必須先修過 ca 才能修 cb；必須先修過 cb 和 cc 才能修 cd；
  必須先修過 cd 才能修 ce。
• John 負責課程 cd，告訴我先修課程為 cc, cb, ca。
• Elizabeth 負責課程 ce，告訴我先修課程為 cd, cc, cb, ca。

但我發現只需要說明先修課程 cc, cb，就可以修 cd 課程，因為 ca 已經在 cb 的先修課程中。同樣地，只需要說明 cd 是 ce 的先修課程即可，因為 cd 已經有 cc, cb, ca 的先修課程條件了。

不幸地，並不是每個同事都給予最小化的先修課程，太多太多的資訊蜂擁而來，希望有個機器人可以幫忙處理這些資訊，並寫告訴我最小化的先修課程。


Input

輸入第一行有一個整數，表示接下來會有多少測資組，至多 1000 組。

每組第一行會有一個整數 k，表示課程總數，而接下來會有 k 行，分別為課程名稱。
課程名稱由小寫英文字母構成，長度最多為 20。

接下來有一個整數 j，表示接下來有 j 行先修課程的資訊。
每一行第一個為課程名稱，第二個整數為先修課程的個數，接下來為先修課程的名稱。

(0 < k, j <= 120)

Output

按照輸入順序，依序輸出該課程的先修課程清單，對於先修課程清單同樣按照輸入順序輸出。

Sample Input

2
5
cc
ca
ce
cb
cd
3
ce 4 cd cb cc ca
cd 3 cb cc ca
cb 1 ca
9
dg
di
dc
df
de
dd
da
dh
db
7
dg 3 da de df
dd 2 da db
df 1 de
dc 1 db
dh 5 da de dg df dc
de 2 da dd
di 2 df dd

Sample Output 

cb 1 ca
cd 2 cb cc
ce 1 cd
dc 1 db
dd 2 da db
de 1 dd
df 1 de
dg 1 df
dh 2 dc dg
di 1 df 

274 - Cat and Mouse

房子中有一隻貓和一隻老鼠，貓和老鼠各自選一間房間為貓窩和鼠窩，牠們會從窩起身到房子的其他房間逛逛，而貓只能通過貓門到另一個房間，而這種貓門都是單向通行的，同樣地，老鼠也有鼠門，牠們只會使用自己的門，不會使用對方的門進出。


給房子地圖資訊，寫程式判斷下面 2 點資訊：

1. 是否存在牠們會碰到面的房間。
2. 老鼠有沒有可能從鼠窩出門(一定要出去到至少一個房間)並且回到鼠窩，途中不會有任何房間有貓的存在疑慮。

例如：從圖中可發現，貓和老鼠可能會在房間 1, 2, 3 碰面，而由於貓不可能出現在房間 4，因此老鼠可以從鼠窩到房間 4 後返回鼠窩。


Input

輸入第一行有一個整數，表示測資組數。測資組間會有一行空行。

對於每組測資第一行會有三個整數 n, cat, mouse，表示房間個數、貓窩、鼠窩編號。
接下來會有數行描述貓門的單向資訊，每行有兩個整數 A, B，表示 A 到 B 存在貓門單向通行，當 A = B = -1，則接下來換鼠門的單向資訊，同樣每行有兩個整數 A, B，表示 A 到 B 存在鼠門單向通行。
 

Ouput

對於每組測資輸出一行，判斷的 2 點資訊，以 'Y' 或 'N' 表示。
測資組間空一行。

Sample Input

1

5 3 5
1 2
2 1
3 1
4 3
5 2
-1 -1
1 3
2 5
3 4
4 1
4 2
4 5
5 4

Sample Output

Y Y

186 - Trip Routing

加州汽車俱樂部(CCC)打算提供會員旅行路線服務，寫一個程式讀取道路資訊以及詢問的兩地，計算出兩地的最短距離。

對於每組詢問， 輸出經過的城市名稱、道路名稱、距離。

Input
 
輸入分成兩個部分，

第一部分描述高速公路的地圖資訊，每一行描述一條高速公路的一小段，用逗號分隔成 4 個欄位，第一欄位表示起點城市名稱，第二欄位表示終點城市名稱，第三欄位表示公路名稱，第四欄位用一個正整數描述公路的長度。

(城市名稱長度最多 20，公路名稱長度最多 10)

第一部分直到空行出現，宣告結束。


第二部分描述詢問的兩地資訊，每一行詢問一組兩地距離，用逗號隔開起點城市與終點城市。

最後用 EOF 最為程式結束。

Output

輸出格式請參考範例輸出，每組詢問前印出 2 個空行。


Sample Input

San Luis Obispo,Bakersfield,CA-58,117
Bakersfield,Mojave,CA-58,65
Mojave,Barstow,CA-58,70
Barstow,Baker,I-15,62
Baker,Las Vegas,I-15,92
San Luis Obispo,Santa Barbara,US-101,106
San Luis Obispo,Santa Barbara,CA-1,113
Santa Barbara,Los Angeles,US-101,95
Bakersfield,Wheeler Ridge,CA-99,24
Wheeler Ridge,Los Angeles,I-5,88
Mojave,Los Angeles,CA-14,94
Los Angeles,San Bernardino,I-10,65
San Bernardino,Barstow,I-15,73
Los Angeles,San Diego,I-5,121
San Bernardino,San Diego,I-15,103

Santa Barbara,Las Vegas
San Diego,Los Angeles
San Luis Obispo,Los Angeles

Sample Output

From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
Santa Barbara        Los Angeles          US-101        95
Los Angeles          San Bernardino       I-10          65
San Bernardino       Barstow              I-15          73
Barstow              Baker                I-15          62
Baker                Las Vegas            I-15          92
                                                     -----
                                          Total        387


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Diego            Los Angeles          I-5          121
                                                     -----
                                          Total        121


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Luis Obispo      Santa Barbara        US-101       106
Santa Barbara        Los Angeles          US-101        95 
                                                     -----
                                          Total        201

1233 - USHER

在紐西蘭的一個大教堂中，每當禮拜結束後，牧師將會給一個收集盒，而這個盒子最多裝 c 元，當教友收到這個盒子時，他將會放入一些錢並且交給下一個教友。現在裡頭混有一個不明人士，每當盒子傳到他手上時，他將會抽出 1 元放入口袋，然後將盒子交給其中一名教友。

每名教友的行為，分別有會傳給哪些教友，以及每次盒子經過時他會放多少錢進去。如果在放的過程中盒子滿了，則將會把盒子立刻地傳到牧師那邊。


計算這個不明人士在最好的情況下，他能偷拿多少錢。

Input

輸入第一行有一個整數，表示接下來會有多少測資組。



每組測資第一行有兩個整數 b, p ，分別表示盒子容量、教友的個數。
(1 <= b <= 1,000,000, 1 <= p <= 500)，教友編號為 1, 2, 3, ..., p，不明人士編號為 0。
接著會有一個整數 q，表示這個不明人士可以傳給其中多少教友，則接下來會有 q 個整數緊接在後，表示不明人士可以傳的教友編號。





接下來會有 p 行，在其中第 i 行表示教友 i 的行為，每行第一個整數表示他會有多少行為，每組行為第一個整數為他放入的金額，第二個整數則表示他放完這筆金額後會傳給的人。


Output

對於每組測資，輸出不明人士最多能拿多少錢。



測資說明：
盒子最多能放 10 元，而有 2 位教友，其中不明人士會傳給 1 或 2。而教友 1 會放入 6 元後傳給不明人士，或者是放入 4 元後傳給教友 2。教友 2 則是會放入 5 元後傳給不明人士。



不明人士打算只傳給教友 2，教友 2 放入 5 元後，被不明人士抽走 1 元，盒子內部只剩 4 元，再進行一次，到不明人士手中時，又抽走 1 元剩下 7 元，最後傳給教友 2 時，放入 5 元已經超過盒子容量便直接傳給牧師收走。
 
Sample Input

1 
10 2 
2 1 2 
2 6 0 4 2 
1 5 0 
0

Sample Output

2

12319 - Edgetown's Traffic Jams

Edgetown 以互相通信為驕傲的城市，也就是說可以從城市的任何一地到達其他所有地方。對於城市的每一條路連接兩個路口，也就是說每條路中間不會有奇他的路口，同時也不會有兩條路兩端連接相同的路口。城市當局每年都必須確保道路的連通性，也就是不會有被孤立的路口，而有些道路是雙向的。



下圖表示有 11 個路口(以 '*' 表示) 和 10 條道路。

最近有幾個地方產生交通壅塞，專家建議將雙向道改成單向道，然而這項工程要特別小心，否則將會有些地方被孤立無法到達，又或者使兩地的最短路徑增大。

經過數次討論，市長的顧問打算同意兩地之間的最短距離增大 A 倍加一個常數 B，也就是說當兩地最短距離 x，更改過後的距離最多為 Ax+B。

寫一個程式，判斷新的建議是否符合市長顧問的要求。


Input

輸入有多組測資，每組測資有兩張圖的描述。
 
每組第一行有一個整數 n (3 <= n <= 100)，表示路口的個數，路口編號為 1, 2, 3, ..., n。

接下來會有 n 行，在第 i 行(1 <= i <= n) 上會有數個整數，表示路口 i 相連到其他路口的資訊。

接下來會有 n 行，在第 i 行(1 <= i <= n) 上會有數個整數，表示在新的規劃中，路口 i 相連到其他路口的資訊。

最後一行會有兩個整數 A, B (0 <= A, B <= 10)

Output

對於每組測資，輸出 "Yes" 或 "No" 表示是否接受新的建議。

Sample Input

5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
1 2
5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
2 0
3
1 2
2 1 3
3 1 2
1 2
2 3
3 1
0 2
0

Sample Output

Yes
No
Yes

1247 - Interstar Transport

到了西元 2100 年，對於銀河系上的太空旅行已經實現了，星際旅行社打算規劃星球旅行，將兩個最受歡迎的星球設計路線，這路線的花費使用 Galaro 為貨幣單位，並且也出了許多不同語言版本，然而並不是任兩個星球都有被規劃路線，兩個星球間的旅行被限制於太空旅行清單中。

幫助旅客規劃他們的行程，星際旅行社想要提供一款行動 App 找到最佳旅行選擇，最加取決於兩個星球間的旅程花費， 給定起點與終點星球，找到一條路徑有最少花費，並且輸出路程中的每一個星球，如果有同一條路具有相同花費時，則找中間經過最少個星球為最佳路徑。每組測資只會存在一組最佳路徑。

條件限制

1. 星球個數 s (1 <= s <= 26)，且每個星球使用大寫英文字母表示 'A', 'B', 'C', ..., 'Z'。
2. 星球間，最多存在 200 條可進行太空旅行的直通道路。
3. 每條路線的花費都是一個正整數小於等於 100。

Input

輸入第一行會有兩個整數 s, p。
接下來會有 p 行，每行上有兩個字元 e_i , e_j 以及一個整數 d_ij
表示 e_i , e_j  間可以進行太空旅行，且花費為 d_ij，
緊接著會有一個整數 n (1 <= n <= 20)，表示有多少組詢問，
接下來會有 n 行，每行上有兩個字元 e_k , e_m，表示要求這兩個星球的最少花費路徑。

Output

對於每組詢問輸出一行，每個星球編號間以空白隔開，順序為從起點到終點從左至右輸出。

Sample Input

5 7 
A B 1
B C 2
C D 3
D E 2
E A 1
A D 3
A C 4
3 
B D 
A D 
E C

Sample Output

B A D 
A D 
E A B C

10724 - Road Construction

孟加拉政府正在思考要如何解決達卡市的塞車問題，他們嘗試很多方向去解決這個問題。

上級長官 了解狀況的嚴重，他們向你求助於不同的看法與解決方法，作為一個資訊領域的你，給他們一個很簡單的想法，建造新的道路即可，但要確保這條新建道路可以使得旅途變短，這樣才能讓自動導航使用這條道路，進而改善塞車問題。

而達卡市的道路相當於無向圖，每個節點、邊分別對應站、道路。節點是由 2-D 平面的幾和點，而經由道路的花費由點與點的歐幾理德距離計算，現在只能新建一條道路，你將選擇其中兩個點建造出一條道路。

• 如果 (u, v)  本來就有一條道路，則不必考慮。
• 反之，C_uv = Sum (PreCost_ij -CurCost_ij)，CurCost_ij 表示加入新道路後的最短距離，而 PreCost_ij 表示之前的最短距離，將所有 i 到 j 都考慮，則最大的 C_uv 將會被選擇去新建。

Input
每組測資第一行有兩個整數 N, M (N <= 50, M <= 1225) ，

接下來會有 N 個點座標 (x, y), (-1000 <= x, y <= 1000)，而接下來會有 M 組 (u, v), (1 <= u, v <= N) 表示 u, v 之間已經有建造的道路。

當 N = M = 0 時，結束程式。

Output
對於每組測資，輸出最大的 C_uv  對應的 (u, v)，其中 u 越小越好，相同時 v 越小越好。

當 C_uv <= 1.0 時，則輸出 “No road required”。

Sample Input	Output for Sample Input
4 6 0 0 0 2 2 0 2 2 1 2 1 3 1 4 2 3 2 4 3 4 4 4 0 0 0 2 2 0 2 2 1 2 2 3 3 4 4 1 4 3 0 0 0 2 2 0 2 2 1 2 2 3 3 4 0 0	No road required 1 3 1 3

---

Problem setter: Md. Kamruzzaman
Member of Elite Problemsetters' Panel
Special thanks to Tahseen Mohammad

1229 - Sub-dictionary

在這個問題中，"dictionary" 字典定義為根據字典順序排序的單字，且每個單字有其相關連的定義，每個單字必然會使用其他單自來解釋，所以當字典定義 N 個單字時，則確切只會出現 N 個單字在字典中，當然不存在單字用來定義自己本身。


"sub-dictionary" 收集字典一部分的單字，當然也會符合上述的條件，而有門計算語言的課程指派一個作業，找到語言最基礎的單字量，並且把它建立成一部字典。 藉此可以推論理解出新的單字。


要讓機器自動學習相當困難，所以我們決定先教他幾個簡單常用的單字，一開始近似於 "sub-dictionary"，而藉由這些單字，機器將會拓展知識，逐步地理解新的單字，直到整個字典的單字都被理解。

例如要理解單字 "xyz" 前，必須理解所有它定義內的所有單字。

寫程式找到一個最小的 "sub-dictionary"。

Input 

輸入有多組測資。

每組測資第一行 有一個整數 n (1 <= n <= 100)，接下來會有 n 行，每行的第一個單字為字典內的單字，接下來會有數個單字表示定義該單字用的詞。

每個英文單字長度不超過 25，且每個單字的定義所需單字不超過 30 個。
而保證一開始給定的字典會符合上的描述。

Output 

對於每組測資，輸出最小字典的大小，接著按照字典順序輸出 sub-dictionary 內的單字。

Sample Input 

5 
aue oizer piqoi oizer 
doy oizer hweqlo hweqlo 
hweqlo piqoi aue 
oizer piqoi 
piqoi aue aue 
0

Sample Output 

3 
aue oizer piqoi

10765 - Doves and bombs

西元 1995 年，已經數年的和平日子，戰爭又即將爆發。

你的國家 Evergreen Macros And Confusing Shortcuts (EMACS) 要保護自己，免得受到鐵路帝國號稱的 Visually Impaired Machinists (VIM) 侵擾。

在這幾天爆發的戰爭中，政府投入大量資源去獲得 VIM 的情報，發現以下幾個資訊：

• VIM 具有龐大的鐵路網路，每個火車站彼此都是雙向連通的。
• 在戰爭爆發之前，每個火車站最多直接連接到另外 10 個火車站。
• VIM 的訊息交換都是藉由鐵路，在戰爭爆發之前，他們都盡可能使用鐵路通訊。
• 為了抵抗戰爭來襲，帝國中央命令可以藉由鴿子來傳遞訊息，但是這將會造成昂貴的負擔。因為鴿子要遠從 Pigeons In Courier Outfits (PICO) 的島嶼進口過來。
• 一旦鴿子抵達其中一個火車站，則就會休息，而且不能再次使用。因此盡可能使用火車來傳輸，而鴿子帶來的訊息將會被鐵路傳輸到其他火車站。

由於這些資訊，EMACS 政府打算擬策計畫來破壞邪惡帝國的活動，他們打算派出轟炸機摧毀火車站，妨礙帝國的訊息通訊，而帝國就必須引入鴿子來協助，藉此分散他們對戰爭的助力。

不幸地， 政府花太多錢在蒐集情報，以至於沒有足夠的錢製作炸彈，於是只能摧毀一個火車站。你要找到最好的候選車站進行催毀，好壞根據 "鴿子值" ，這個鴿子值定義：當一個火車站被摧毀後，中央至少要派幾隻鴿子進行傳輸的工作，才能傳遞到所有未摧毀的火車站

由於不知道中央指揮部在哪，也就是說他們至少一定會使用一個鴿子將訊息傳遞到一個未摧毀的火車站，再經由鐵路傳遞到更遠的火車站。

Input

輸入有多組測資，每組第一行有兩個整數 n, m。

• n：(3 <= n <= 10000) 表示帝國火車站個數，且編號從 0 到 n-1 。
• m：(1 <= m <= n) 表示要挑選候選的個數。

接下來會有數行表示鐵路連接資訊，每行 (x,y)，表示 x 和 y 相連，直到 x = y = -1 表示資訊結束。

當 n = m = 0 結束程式。

Output

對於每組測資，輸出 m 行，輸出候選火車站的資訊，根據鴿子值由高到低，相同時則按照鴿子值由小到大，只要輸出前 m 個即可。

每組測資後輸出一行空行。

Sample Input                             Output for Sample Input

8 4 0 4 1 2 2 3 2 4 3 5 3 6 3 7 6 7 -1 -1 0 0

2 3 3 3 4 2 0 1

---

Problemsetter: Paul Shelly

610 - Street Directions

根據汽車碰撞監測，很多致命的交通事故發生於雙向通行街道，為了減少意外事故的發生，市長決定要使盡可能多的街道變成單向，你被雇用來解決這個問題。

一開始給定一些雙向的道路，每個道路連接兩個十字路口，並且中間不會經過其他十字路口，每個路口最多 4 個街道相連，而最多只會有一條道路連接至相同的路口，也有可能道路的尾端是死路，當都是雙向道路時，任兩個目的地都可以相鄰。

Input 

測資有多組。

每組第一行有兩個整數 n, m (2 <= n <= 1000)，接下來會有 m 行表示雙道道路的資訊，每行上有兩個整數 i j，表示路口 i 和 j 互相連接。而路口的編號為 1 到 n。

當 n = m= 0 結束程式。

Output 

對於每組測資，先輸出測資組編號。緊接著依序輸出單向訊息 i, j ，表示 i 可以通往道 j。
因此輸出 i, j 不同於 j, i 的意思。

每組測資後輸出一個 '#' 字元。


任何一組符合解都可以被接受。

Sample Input 

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
0 0

Sample Output 

1

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
2

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#

---

Miguel A. Revilla
1999-03-24

848 - Fmt

 在 unix 系統中，有一個 fmt  程式，用來處理文字顯示，結合許多行，或者是將行與行之間分行，而且每一行最多 72 個字元(含)，處理結合行與分行的規則如下：

備註翻譯：想像文章中的段落，以下翻譯改編題目意思，因為看不懂，請高人指點。

• 對於一個新段落，一開始可能會有許多空白，而段落最後不會存在多餘的空白。
  
  
• 分行字元 '\n' 將不會在輸入時顯示，而在輸出部分，段落可能占有數行，其中的每一行尾端不會存在空白。在段落結束前，每一行一開始將不會有任何空白或者空行。如果輸入的 '\n' 字元被結合成一行時，則替換成一個空白進行串接。
• 每的字詞不超過 72 個字元，也就是再長的字元最多占有一行。
  
• 每個字詞不允許跨行，一定要在同一行顯示。

Sample Input 

   Unix fmt

The unix fmt program reads lines of text, combining
and breaking lines so as to create an
output file with lines as close to without exceeding
72 characters long as possible.  The rules for combining and breaking
lines are as follows.

   1.  A new line may be started anywhere there is a space in the input.
If a new line is started, there will be no trailing blanks at the
end of the previous line or at the beginning of the new line.

   2.  A line break in the input may be eliminated in the output, provided
it is not followed by a space or another line break.  If a line
break is eliminated, it is replaced by a space.

Sample Output 

   Unix fmt

The unix fmt program reads lines of text, combining and breaking lines
so as to create an output file with lines as close to without exceeding
72 characters long as possible.  The rules for combining and breaking
lines are as follows.

   1.  A new line may be started anywhere there is a space in the input.
If a new line is started, there will be no trailing blanks at the end of
the previous line or at the beginning of the new line.

   2.  A line break in the input may be eliminated in the output,
provided it is not followed by a space or another line break.  If a line
break is eliminated, it is replaced by a space.

---

Miguel Revilla 2002-06-15

168 - Theseus and the Minotaur

在希臘神話中，有一個傳說「忒修斯(Theseus)和牛頭怪」 這是一個不太可能的故事，故事中參雜了一個牛頭的怪物、充滿曲折的地下迷宮、失戀的女孩以及線球。在這次競賽的教育性質上，我們要揭露這個真實故事。

迷宮有很多洞窟，每個洞窟經由幾個通道可以通往其他洞窟，而其中幾個只能單向通行。為了設下陷阱抓到牛頭怪，忒修斯發現牛頭怪怕光，於是帶著大量的蠟燭進入迷宮。

忒修斯在迷宮四處找尋，最後他聽到牛頭怪從通道另一端傳來的聲音，從那個時刻開始，忒修斯點燃蠟燭並且展開追逐行動，牛頭怪會離開原本的洞窟，並且移動到下一個洞窟。而忒修斯慢慢地跟著牛頭怪移動，當每經過 k 個洞窟，他將會在此點燃一個蠟燭放下，當他快速點燃蠟燭後，會繼續跟蹤牛頭怪。由於有蠟燭的洞窟牛頭怪不會靠近，因此將會限制住牛頭怪的移動。

當牛頭怪離開洞窟時，會依序檢察其它不存在蠟燭的洞窟，找到第一個可去的地方並且移動，最後牛頭怪會被困住無法移動，忒修斯將可以戰勝牠。

迷宮類似於下圖表示，而牛頭怪離開的時候就好比按照字典順序檢查：

假設忒修斯在 C，他會聽到牛頭怪從 A 傳來的聲音，假設 k = 3，而走的順序依序為 A, B, D(忒修斯在此放下點燃的蠟燭), G, E, F(再放一個), H, E, G(再放一個), H, E(牛頭怪最後受困的地點)。

備註翻譯：由於忒修斯尾隨牠，牛頭怪不會走回上次的洞窟。



寫一個程式模擬整個追逐過程，所有洞窟將只會用大寫英文字母表示，並且按照順序打印出蠟燭的放置，以及最後牛頭怪被困的洞窟。

Input

輸入有多組測資，每組用一行表示圖形以及忒修斯位置、牛頭怪位置、k。

每一行不超過 255 個字元。

讀到 '#' 結束程式。

Output

對於每組測資，按照順序輸出蠟燭的放置(追逐時的順序)，以及牛頭怪最後的位置。

Sample input

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
#

Sample output

D F G /E

10690 - Expression Again

給定一個代數方程 (x1+x2+x3+.....+xn)*(y1+y2+.........+ym) ，其中會有 n+m 個整數，必須要找到可以代出的 最大值 和 最小值。例如：給定  (x1+x2)*(y1+y2)，而能使用的數字為 1, 2, 3, 4，每個數字只能使用一次，則最大值為  (1+4)*(2+3) = 25，最小值則為 (4+3)*(2+1) = 21。

Input

對於每組測資，給定兩個正整數 N, M (N, M < 51)，接下來會有 N+M 個整數，每個數字介於 -50 到 50 之間(含)。

測資最多 110 組。

Output

對於每組測資，輸出一行最大值以及最小值。

Sample Input                           Output for Sample Input

2 2 1 2 3 4 3 1 1 2 3 4 2 2 2 2 2 2

25 21 24 9 16 16

---

Problem setter: Md Kamruzzaman, Member of Elite Problemsetters' Panel

Special Thanks: Monirul Hasan, Md. Sajjad Hossain

11664 - Langton's Ant

數學家 Christopher Langton 設計一套簡單的細胞自動機，名為 Langton's ant，根據給定的一個簡單行為規則但卻有趣的行為，這個行為是數學家研究的課題。


從分析螞蟻行為以及 Langton 的細胞自動機，根據給定的當下自動機的狀態，以及全自動的螞蟻能力，將會發現螞蟻呈現一個特別的走訪模式，進行探索這個世界。

螞蟻的世界為一個 n x n 的平面，每一格塗上藍色或者是紅色，而每一格座標定義 (i, j) (1 <= i, j <= n)，螞蟻的移動規則如下：

• 如果當前在藍色格子，她會將格子變成紅色，並且向左轉 90 度，並且朝這個方向前進一格。
• 如果當前在藍色格子，她會將格子變成紅色，並且向右轉 90 度，並且朝這個方向前進一格。
• 如果移動失敗，即掉出格子外，螞蟻則宣告死亡。

例如：假設有一隻螞蟻現在在紅色格子上，並且面朝東方，而牠會將這格變成紅色，並且面朝南方，如果南方沒有格子可走，那麼牠則會死亡 。反之，則會走下南方的那一格，並且重複步驟進行移動。


根據給定的狀態以及當前螞蟻所在位置，你的任務是要決定螞蟻能不能到達 (n, n)。

假設螞蟻一開始面朝北方。

Input 

由於狀態是 n x n ，可以表示 n² bits 的二進制數字，方便起見定義 0 是藍色，1 是紅色。而給定的順序為由左而右、由下而上。

例如：0100 (十進制為 4) 表示一個 2 x 2 的狀態

blue	blue
blue	red

而  011010100 (十進制為 212) 表示一個 3 x 3 的狀態

red	blue	blue
blue	red	blue
blue	red	red

額外補充：相對應座標如下 (x, y)

(3,1)	(3,2)	(3,3)
(2,1)	(2,2)	(2,3)
(1,1)	(1,2)	(1,3)

輸入有多組測資，每組測資第一行會有四個整數 n, c, x, y

• n ( 1 <=  n  <= 16)：狀態的大小
• c ( 0 <= c  < 2⁽ⁿ²⁾)：一個十進制表示  n²-bit 二進制數，其數值為上描述。
• (x, y)：表示螞蟻一開始所在的位置 (1 <= x, y <= n)。

當 n = c = x = y = 0 結束程式。

Output 

對於每組測資，輸出格式為以下兩種的其中一種：

• `Yes'：如果螞蟻能夠抵達 (n, n)
• `Kaputt!'：如果螞蟻無法抵達 (n, n)

對於每組測資，保證一定會在有限步數內得到其中一種結果。

Sample Input 

2 8 1 1
2 4 1 1
2 15 1 1
0 0 0 0

Sample Output 

Yes
Kaputt!
Kaputt!

---

10992 - The Ghost of Programmers

西元 2500 年，Dhaka 學校的資工系系主任向大學新鮮人介紹：「這是一個 Dhaka 學校中最古老的一棟建築，而我們從來沒有進去過」接著學生好奇地向他問道「為什麼沒進去過？」主任回答道：「這個原因追溯到 21 世紀，我們那時常在這裡舉辦程式設計競賽，當時所有的出題者們常會來到這裡，由於他們太喜歡這個地方了，以至於連他們死後也會來這裡！」學生緊接著問道「先生，有多少鬼魂會來到這呢？」主任回答「沒人知道有多少，但有九個最常見的鬼會出現！」

0. The ghost of Tanveer Ahsan – 每隔 2 年出現一次。

1. The ghost of Shahriar Manzoor - 每隔 5 年出現一次。

2. The ghost of Adrian Kugel - 每隔 7 年出現一次。

3. The ghost of Anton Maydell - 每隔 11 年出現一次。

4. The ghost of Derek Kisman - 每隔 15 年出現一次。

5. The ghost of Rezaul Alam Chowdhury - 每隔 20 年出現一次。

6. The ghost of Jimmy Mardell - 每隔 28 年出現一次。

7. The ghost of Monirul Hasan - 每隔 36 年出現一次。

最後一隻鬼最特別，他來得頻率最高！

8. The ghost of K. M. Iftekhar - 每逢閏年必來！

而學生問什麼時候全部的鬼都會同時來？回答道「在西元 2148 年，所有的鬼第一次集合於此！」(即在西元 2148 年前，出題者可能還沒死。)

給定一個年份，求當年有哪些鬼會來。 

Input

測資最多 250 筆。

每一行有一個正整數 Y，Y 最多 55 位(64-bit 至多 20 位)。

當 Y = 0 結束程式。

Output

對於每組測資，先輸出 Y，根據名稱的順序輸出有哪些鬼來，格式為 "Ghost of G!!!"。

如果當年沒有任何一個鬼來，則輸出  "No ghost will come in this year"。

測資組間空一行。

Sample Input                               Output for Sample Input

2500 3000 0

2500 Ghost of Tanveer Ahsan!!! Ghost of Anton Maydell!!! 3000 Ghost of Tanveer Ahsan!!!

---

Problem setter: K. M. Iftekhar

Moderator: Shahriar Manzoor, EPS