b065. 4. 滿漢全席
內容 ：
滿漢全席是中國最豐盛的宴客菜餚，有許多種不同的材料透過滿族或是漢族的料理方式，呈現在數量繁多的菜色之中。由於菜色眾多而繁雜，只有極少數博學多聞技藝高超的廚師能夠做出滿漢全席，而能夠烹飪出經過專家認證滿漢全席，也是中國廚師最大的榮譽之一。
世界滿漢全席協會是由能夠料理滿漢全席的專家廚師們所組成，而他們之間還細分為許多不同等級的廚師。為了招收新進的廚師進入世界滿漢全席協會，將於近日舉辦滿漢全席大賽，協會派遣許多會員當作評審，為了就是要在參賽的
廚師之中，找到滿漢料理界的明日之星。
大
會的規則是這樣的，將發給參賽的選手n 種材料，而選手可以自由選擇將材料利用滿式或是漢式其中一種料理當成菜餚。而大會的評審制度是這樣的，有m
位評審分別把關。每一位評審對於滿漢全席有各自獨特的見解，心裡頭都覺得在這些材料的限制下，有兩樣菜色是作為滿漢全席是不能缺少的，如某評審認為，如果
沒有漢式東坡肉跟滿式的涮羊肉鍋，就不能算是滿漢全席。但避免過於有主見的審核，一個評審除非是兩樣心目中必備的菜色都沒有做出來的狀況下，否則是不會淘
汰該參賽者的。換句話說，只要參賽者能在這兩種材料的做法中，其中一個符合評審的喜好即可通過該評審的審查。如材料有豬肉，羊肉和牛肉時，有四位評審的喜
好如下表：
| 評審一 | 評審二 | 評審三 | 評審四 |
| 滿式牛肉 | 滿式豬肉 | 漢式牛肉 | 漢式牛肉 |
| 漢式豬肉 | 滿式羊肉 | 漢式豬肉 | 滿式羊肉 |
如參賽者甲做出滿式豬肉，滿式羊肉和滿式牛肉料理，他將無法滿足評審三的要求，無法通過評審。而參賽者乙做出漢式豬肉，滿式羊肉和滿式牛肉料理，就可以滿足所有評審的要求。
但大會後來發現，在這樣的制度下如果材料選擇跟派出的評審沒有特別安排好的話，所有的參賽者最多只能通過部分評審的審查而不是全部，所以可能會發生沒有人通過考驗的情形。如有四個評審喜好如下表時，則不論參賽者採取什
麼樣的做法，都不可能通過所有評審的考驗：
| 評審一 | 評審二 | 評審三 | 評審四 |
| 滿式羊肉 | 滿式豬肉 | 漢式羊肉 | 漢式羊肉 |
| 漢式豬肉 | 滿式羊肉 | 漢式豬肉 | 滿式豬肉 |
所以大會希望有人能寫一個程式來判斷，所選出的 m 位評審，會不會發生沒有人能通過考驗的窘境，以便協會挑選合適的評審團。
輸入說明
：
50 組測試資料，而每筆測試資料中材料的種類數跟評審的個數均不超過15。
輸出說明
：
每筆測試資料輸出一行，如果不會發生沒有人能通過考驗的窘境，輸出GOOD；否則輸出BAD。
範例輸入 ：
2 3 4 m3 h1 m1 m2 h1 h3 h3 m2 2 4 h1 m2 m2 m1 h1 h2 m1 h2 2 3 3 h1 m3 h3 m2 m3 m1 3 3 h1 m2 h2 m3 h3 m1
範例輸出 ：
GOOD BAD GOOD GOOD
提示
：
出處
：
作法 : 窮舉
窮舉 O (2^n)
/**********************************************************************************/
/* Problem: b065 "4. 滿漢全席" from 94全國資訊學科能力決賽 */
/* Language: C */
/* Result: AC (6ms, 182KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-22 11:04:02 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
struct Data{
int like[2];
}judge[30];
int flag, n, m, Used[100] = {};
void DFS(int tn) {
if(flag) return;
if(tn == n+1) {
int a;
for(a = 0; a < m; a++) {
if(Used[judge[a].like[0]] == 0 && Used[judge[a].like[1]] == 0)
break;
}
if(a == m) flag = 1;
return;
}
Used[tn*2] = 1;
DFS(tn+1);
Used[tn*2] = 0;
Used[tn*2+1] = 1;
DFS(tn+1);
Used[tn*2+1] = 0;
}
main() {
int k, a, b;
char x[10], y[10];
while(scanf("%d", &k) == 1) {
while(k--) {
scanf("%d %d", &n, &m);
for(a = 0; a < m; a++) {
scanf("%s %s", x, y);
int t;
for(b = 1, t = 0; x[b]; b++) t = t*10 + x[b]-'0';
judge[a].like[0] = t*2+(x[0] == 'h');
for(b = 1, t = 0; y[b]; b++) t = t*10 + y[b]-'0';
judge[a].like[1] = t*2+(y[0] == 'h');
}
flag = 0, DFS(1);
puts(flag ? "GOOD" : "BAD");
}
}
return 0;
}