题目
满汉全席是中国最丰盛的宴客菜肴，有许多种?同的材?透过满族或是汉族的??方式，呈现在??繁多的菜色之中。由于菜色众多而繁杂，只有极少?博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。 世界满汉全席协会是由能够??满汉全席的专家厨师们所组成，而他们之间还细分为许多?同等级的厨师。为?招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在?赛的厨师之中，找到满汉??界的明日之星。 大会的规则如下：每位?赛的选手可以得到n 种材?，选手可以自由选择用满式或是汉式??将材?当成菜肴。大会的评审制?是：共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的?解，但基本见解是，要有?样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就?能算是满汉全席。但避免过于有主?的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出?的?况下，才能淘汰一位选手，否则?能淘汰一位?赛者。换?话?，只要?赛者能在这?种材?的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材?有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表： 评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉 如?赛者甲做出满式猪肉，满式羊肉和满式牛肉??，他将无法满足评审三的要求，无法通过评审。而?赛者乙做出汉式猪肉，满式羊肉和满式牛肉??，就可以满足所有评审的要求。 但大会后?发现，在这样的制?下如果材?选择跟派出的评审员没有特别安排好的话，所有的?赛者最多只能通过部分评审员的审查而?是全部，所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时，则???赛者采取?么样的做法，都?可能通过所有评审的考核： 评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉 所以大会希望有人能写一个程序?判断，所选出的m 位评审，会?会发生 没有人能通过考核的窘境，以?协会组织合适的评审团。
输入格式
第一?包含一个数字 K，代表测试文件包含?K 组资?。每一组测试资?的第一?包含?个数字n 跟m（n≤100，m≤1000），代表有n 种材?，m 位评审员。为方?起?，材?舍弃中文名称而给予编号，编号分别从1 到n。接下?的m ?，每?都代表对应的评审员所拥有的?个喜好，每个喜好由一个英文字母跟一个数字代表，如m1 代表这个评审喜欢第1 个材?透过满式??做出?的菜，而h2 代表这个评审员喜欢第2 个材?透过汉式??做出?的菜。每个测试文件?会有超过50 组测试资?
输出格式
每笔测试资?输出一?，如果?会发生没有人能通过考核的窘境，输出GOOD；否则输出BAD（大写字母）。
输入样例
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2
输出样例
GOOD
BAD
题解
一句话题意：
有n个物品，每个物品赋予’h’或’m’一种属性。有m个二元限制：“某物品必须是某属性”，要求每个二元限制至少满足一个，问是否有解
经典的2-sat问题，是一个入门题【都不用输出方案。。。】
对于每个限制，我们如果不选第一个就必须选第二个
我们把物品分为两个点分别表示两种属性。显然一个物品不能同时具有两个属性，所以它们是互斥的。对于每对限制，两个点分别向另一个点的相对点连有向边，2-sat判断一下就好
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 205,maxm = 100005,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {
if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {
out = (out << 3) + (out << 1) + c - '0'; c = getchar();}return out * flag;
}
int get(){char c = getchar();while (c != 'm' && c != 'h') c = getchar();return 2 * RD() - (c == 'h');
}
int n,m,h[maxn],ne = 0;
struct EDGE{
int to,nxt;}ed[maxm];
inline void build(int u,int v){ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
}
int dfn[maxn],low[maxn],Scc[maxn],scci,cnt,st[maxn],top = 0;
void dfs(int u){dfn[u] = low[u] = ++cnt;st[++top] = u;Redge(u){if (!dfn[to = ed[k].to])dfs(to),low[u] = min(low[u],low[to]);else if (!Scc[to]) low[u] = min(low[u],dfn[to]);}if (dfn[u] == low[u]){scci++;do{Scc[st[top]] = scci;}while (st[top--] != u);}
}
int main(){int T = RD(),x,y,u,v,flag;while (T--){n = RD(); m = RD(); flag = true;ne = scci = cnt = 0;REP(i,n << 1) dfn[i] = h[i] = Scc[i] = 0;while (m--){x = get(); y = get();u = (x & 1) ? x + 1 : x - 1;v = (y & 1) ? y + 1 : y - 1;build(x,v); build(y,u);}REP(i,n << 1) if (!dfn[i]) dfs(i);REP(i,n) if (Scc[2 * i] == Scc[2 * i - 1]){flag = false; break;}if (flag) puts("GOOD");else puts("BAD");}return 0;
}