Description
满汉全席是中国最丰盛的宴客菜肴，有许多种?同的材?透过满族或是汉族的??方式，呈现在??繁多的菜色之中。由于菜色众多而繁杂，只有极少?博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。
世界满汉全席协会是由能够??满汉全席的专家厨师们所组成，而他们之间还细分为许多?同等级的厨师。为?招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在?赛的厨师之中，找到满汉??界的明日之星。
大会的规则如下：每位?赛的选手可以得到n 种材?，选手可以自由选择用满式或是汉式??将材?当成菜肴。大会的评审制?是：共有m
位评审员分别把关。每一位评审员对于满汉全席有各自独特的?解，但基本见解是，要有?样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就?能算是满汉全席。但避免过于有主?的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出?的?况下，才能淘汰一位选手，否则?能淘汰一位?赛者。换?话?，只要?赛者能在这?种材?的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材?有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表：
评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉
如?赛者甲做出满式猪肉，满式羊肉和满式牛肉??，他将无法满足评审三的要求，无法通过评审。而?赛者乙做出汉式猪肉，满式羊肉和满式牛肉??，就可以满足所有评审的要求。
但大会后?发现，在这样的制?下如果材?选择跟派出的评审员没有特别安排好的话，所有的?赛者最多只能通过部分评审员的审查而?是全部，所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时，则???赛者采取?么样的做法，都?可能通过所有评审的考核：
评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉
所以大会希望有人能写一个程序?判断，所选出的m 位评审，会?会发生 没有人能通过考核的窘境，以?协会组织合适的评审团。
Input
第一?包含一个数字 K，代表测试文件包含?K 组资?。每一组测试资?的第一?包含?个数字n 跟m（n≤100，m≤1000），代表有n
种材?，m 位评审员。为方?起?，材?舍弃中文名称而给予编号，编号分别从1 到n。接下?的m
?，每?都代表对应的评审员所拥有的?个喜好，每个喜好由一个英文字母跟一个数字代表，如m1 代表这个评审喜欢第1
个材?透过满式??做出?的菜，而h2 代表这个评审员喜欢第2 个材?透过汉式??做出?的菜。每个测试文件?会有超过50 组测试资?
Output
每笔测试资?输出一?，如果?会发生没有人能通过考核的窘境，输出GOOD；否则输出BAD（大写字母）。
Sample Input
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2
Sample Output
GOOD
BAD
题解
吐槽一把
贼长贼长的题面
其实就是一堆材料，然后每个材料可以做成两种东西，一堆人提出要求，只要有一个东西是满足要求的话那么这个人的要求可以满足。我们想知道可不可以满足所有人的要求
原谅我开始想了很久的网络流最后当然无果
后来再看看其实不就是2-sat嘛。。
一种材料做成了一种东西，那么另外一种东西肯定不可能被做出来。。
于是乎我们按照要求连边。材料拆点i*2,i*2+1，表示满族和汉族
比如一个人的要求是m1 h2
那么就1*2+1->2*2，以及2*2+1->1*2
因为第一种材料做了汉族的，那么第二种材料一定做满族。。不然就不能满足这个人的要求
另外一条边同理
跑一边tarjan缩点，枚举每种材料的满族汉族做法是不是在一个连通分量里，是就不能满足。不是就ok
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int x,y,next;
}a[111000];int len,last[11100];
void ins(int x,int y)
{len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;
}
int low[11000],dfn[11000],sta[11000],id,tp;
bool v[11000];
int belong[11000],cnt;
void dfs(int x)
{low[x]=dfn[x]=++id;v[x]=true;sta[++tp]=x;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(dfn[y]==-1){dfs(y);low[x]=min(low[x],low[y]);}else{if(v[y]==true)low[x]=min(low[x],dfn[y]);}}if(low[x]==dfn[x]){cnt++;int i;do{i=sta[tp--];belong[i]=cnt;v[i]=false;}while(i!=x);}
}
int n,m;
char s1,s2,cc;
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);len=0;memset(last,0,sizeof(last));//满 2*i 汉 2*i+1 for(int i=1;i<=m;i++){int p,q;scanf("\n%c%d %c%d",&s1,&p,&s2,&q);int tmpx,tmpy;if(s1=='m')tmpx=0;else tmpx=1;if(s2=='m')tmpy=0;else tmpy=1;ins(p*2+(1-tmpx),q*2+tmpy);ins(q*2+(1-tmpy),p*2+tmpx);}memset(v,false,sizeof(v));memset(low,0,sizeof(low));memset(dfn,-1,sizeof(dfn));memset(belong,0,sizeof(belong));id=cnt=tp=0;for(int i=2;i<=2*n+1;i++)if(dfn[i]==-1)dfs(i);bool bk=false;for(int i=1;i<=n;i++)if(belong[2*i]==belong[2*i+1])bk=true;if(bk==false)printf("GOOD\n");else printf("BAD\n");}return 0;
}