TopCoder

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

71.8% (28/39)

Description

滿漢全席是中國最豐盛的宴客菜餚,有許多種不同的材料透過滿族或是漢族的料理方式,呈現在數量繁多的菜色之中。由於菜色眾多而繁雜,只有極少數博學多聞技藝高超的廚師能夠做出滿漢全席,而能夠烹飪出經過專家認證滿漢全席,也是中國廚師最大的榮譽之一。

世界滿漢全席協會是由能夠料理滿漢全席的專家廚師們所組成,而他們之間還細分為許多不同等級的廚師。為了招收新進的廚師進入世界滿漢全席協會,將於近日舉辦滿漢全席大賽,協會派遣許多會員當作評審,為了就是要在參賽的廚師之中,找到滿漢料理界的明日之星。

大會的規則是這樣的,將發給參賽的選手n 種材料,而選手可以自由選擇將材料利用滿式或是漢式其中一種料理當成菜餚。而大會的評審制度是這樣的,有m 位評審分別把關。每一位評審對於滿漢全席有各自獨特的見解,心裡頭都覺得在這些材料的限制下,有兩樣菜色是作為滿漢全席是不能缺少的,如某評審認為,如果沒有漢式東坡肉跟滿式的涮羊肉鍋,就不能算是滿漢全席。

但避免過於有主見的審核,一個評審除非是兩樣心目中必備的菜色都沒有做出來的狀況下,否則是不會淘汰該參賽者的。換句話說,只要參賽者能在這兩種材料的做法中,其中一個符合評審的喜好即可通過該評審的審查。如材料有豬肉,羊肉和牛肉時,有四位評審的喜好如下表:

評審一  評審二  評審三  評審四
滿式牛肉 滿式豬肉 漢式牛肉 漢式牛肉
漢式豬肉 滿式羊肉 漢式豬肉 滿式羊肉

如參賽者甲做出滿式豬肉,滿式羊肉和滿式牛肉料理,他將無法滿足評審三的要求,無法通過評審。而參賽者乙做出漢式豬肉,滿式羊肉和滿式牛肉料理,就可以滿足所有評審的要求。

但大會後來發現,在這樣的制度下如果材料選擇跟派出的評審沒有特別安排好的話,所有的參賽者最多只能通過部分評審的審查而不是全部,所以可能會發生沒有人通過考驗的情形。如有四個評審喜好如下表時,則不論參賽者採取什麼樣的做法,都不可能通過所有評審的考驗:

評審一  評審二  評審三  評審四
滿式羊肉 滿式豬肉 漢式羊肉 漢式羊肉
漢式豬肉 滿式羊肉 漢式豬肉 滿式豬肉

所以大會希望有人能寫一個程式來判斷,所選出的m 位評審,會不會發生沒有人能通過考驗的窘境,以便協會挑選合適的評審團。

Input Format

測試檔案的第一行包含一個數字K,代表測試檔案包含了K 組資料。

每一組測試資料的第一行包含兩個數字n 跟m,代表有n 種材料,m 位評審。為方便起見,材料捨棄中文名稱而給予編號,編號分別從1 到n。接下來的m 行,每行都代表對應的評審所擁有的兩個喜好,每個喜好由一個英文字母跟一個數字代表,如m1 代表這個評審喜歡第1 個材料透過滿式料理做出來的菜,而h2 代表這個評審喜歡第2 個材料透過漢式料理做出來的菜。

每個測試檔案不會有超過50 組測試資料,而每筆測試資料中材料的種類數跟評審的個數均不超過15。

Output Format

每筆測試資料輸出一行,如果不會發生沒有人能通過考驗的窘境,輸出
GOOD;否則輸出BAD。

Sample Input

輸入範例1:
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2

輸入範例2:
2
3 3
h1 m3
h3 m2
m3 m1
3 3
h1 m2
h2 m3
h3 m1

Sample Output

輸出範例1:
GOOD
BAD

輸出範例2:
GOOD
GOOD

Hints

Problem Source

原TIOJ1149 / 94全國賽(prob 4)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536
1 30000 65536 65536
2 30000 65536 65536
3 30000 65536 65536
4 30000 65536 65536