记录编号	549596	评测结果	AAAAA
题目名称	[JSOI 2010]满汉全席	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2020-02-16 19:22:54	内存使用	14.04 MiB

#include<bits/stdc++.h>
    #define intw long long
    #define re register
    #define il inline
    #define inf 1e9
    #define eps 1e-15
    #define ll long long
    #define mod 1000000
    #define bianli for(int i=head[x];i;i=a[i].next)
    #define QWQ cout<<"qwq"
    #define me(qw) memset(qw,0,sizeof(qw));
    #define meinf(qw) memset(qw,0x3f,sizeof(qw));
    using namespace std;
    const int maxn=1e4+5;
    int head[maxn],tot,flag;
    struct road{int to,next;}a[maxn*2];
	void add(int x,int y){
	a[++tot].to=y;
	a[tot].next=head[x];head[x]=tot;}
    int vis[maxn],top,tmp,dfn[maxn],low[maxn],col[maxn],qwq,sta[maxn],cnt;
    void tarjan(int x){
   	dfn[x]=low[x]=++cnt;
   	vis[x]=1;
   	sta[++top]=x;
   	for(int i=head[x];i;i=a[i].next){
   	int to=a[i].to;
   	if(!dfn[to]){
   	tarjan(to);
   	low[x]=min(low[x],low[to]);}
   	else if(vis[to]) low[x]=min(low[x],dfn[to]);}
   	if(dfn[x]==low[x]){
   	++qwq;
   	do{
   	tmp=sta[top--];
   	col[tmp]=qwq;	
   	vis[tmp]=0;}while(tmp!=x);}}
   	void init(){
	tot=qwq=top=cnt=flag=0;
	me(head);me(col);me(dfn);me(low);me(vis);me(sta);
   	}
    signed main(){
	freopen("JSOI2010.in","r",stdin);
    freopen("JSOI2010.out","w",stdout);
	char s1[5],s2[5];
	int T,n,m,q,w,e,r,tmp1,tmp2,k;
	cin>>T;
	while(T--){
	init();
	cin>>n>>m;
	while(m--){
	//han +n
	cin>>s1>>s2;
	tmp1=tmp2=0;
	k=1; while(s1[k]>='0'&&s1[k]<='9')tmp1=tmp1*10+s1[k++]-'0';
    k=1; while(s2[k]>='0'&&s2[k]<='9')tmp2=tmp2*10+s2[k++]-'0';
	if(s1[0]=='m'){
	if(s2[0]=='m')add(tmp1+n,tmp2),add(tmp2+n,tmp1);
	else add(tmp1+n,tmp2+n),add(tmp2,tmp1);}
	else{
	if(s2[0]=='m') add(tmp1,tmp2),add(tmp2+n,tmp1+n);
	else add(tmp1,tmp2+n),add(tmp2,tmp1+n);}}
	
	for(int i=1;i<=n*2;i++)
	if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
	if(col[i]==col[i+n]){
	cout<<"BAD"<<endl;flag=1;break;}
	if(!flag)
	cout<<"GOOD"<<endl;}
	return 0;
}