2013年8月13日 星期二

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 的先修課程中。同樣地,只需要說明 cdce 的先修課程即可,因為 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
 

沒有留言:

張貼留言