记录编号	584173	评测结果	AAAAA
题目名称	[JSOI 2010]满汉全席	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2023-11-01 21:12:21	内存使用	2.43 MiB

#include <bits/stdc++.h>
using namespace std;
//tarjan + 2+SAT
//不用输出方案真好 嘻嘻 
const int N = 2e3+10,M = 2e4+10;
int t,n,m;
struct made{
	int ver,nx;
}e[M<<1];
int hd[N],tot,cnt,top,num;
int low[N],dfn[N],c[N],st[N];
bool v[N];
void add(int x,int y){
	tot++;
	e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void tarjan(int x){
	low[x] = dfn[x] = ++cnt;
	v[x] = 1,st[++top] = x;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(!dfn[y])tarjan(y),low[x] = min(low[x],low[y]);
		else if(v[y])low[x] = min(low[x],dfn[y]);
	}
	if(low[x] == dfn[x]){
		++num;int y = 0;
		do{
			y = st[top--];
			v[y] = 0,c[y] = num;
		}while(x != y);
	}
}// 
void first(){
	tot = cnt = num = top = 0;
	memset(e,0,sizeof(e));
	memset(hd,0,sizeof(hd));
	memset(v,0,sizeof(v));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(c,0,sizeof(c));
}//初始化 
int main(){
	freopen("JSOI2010.in","r",stdin);
	freopen("JSOI2010.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		first();
		//以x节点为汉式，x+n节点为满式 
		for(int i = 1;i <= m;i++){
			char a,b;int x,y;
			cin>>a>>x>>b>>y;
			if(a == 'm' && b == 'm')add(x,y+n),add(y,x+n);
			if(a == 'm' && b == 'h')add(x,y),add(y+n,x+n);
			if(a == 'h' && b == 'm')add(x+n,y+n),add(y,x);
			if(a == 'h' && b == 'h')add(x+n,y),add(y+n,x);
		}
		for(int i = 1;i <= 2*n;i++)
		    if(!dfn[i])tarjan(i);
	    bool f = 1;
		for(int i = 1;i <= n;i++){
			if(c[i] == c[i+n]){// 
				printf("BAD\n");
				f = 0;break;
			}
		}
		if(f)printf("GOOD\n");
	}
	
	return 0;
	
}