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