悬关

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
vector<int> g[N];
stack<int> s;
int n,m,dfn[N],vis[N],low[N],color[N],num[N],colornum,cnt;
void paint(int x)
{
	s.pop();
	color[x]=colornum;
	num[colornum]++;
	vis[x]=0;
	return;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++cnt;
	s.push(x);
	vis[x]=true;
	for(auto q:g[x])
	{
		if(!dfn[q])
		{
			tarjan(q);
			low[x]=min(low[x],low[q]);
		}
		else if(vis[q])
			low[x]=min(low[x],dfn[q]);
	}
	if(low[x]==dfn[x])
	{
		colornum++;
		while(s.top()!=x)
		{
			int t=s.top();
			paint(t);
		}
		paint(x);
	}
	return;
}
void init(int pp)
{
	colornum=cnt=0;
	memset(dfn,0,sizeof dfn);
	memset(vis,0,sizeof vis);
	memset(low,0,sizeof low);
	memset(color,0,sizeof color);
	memset(num,0,sizeof num);
	while(!s.empty())
	{
		s.pop();
	}
	for(int i=0;i<=pp*2;i++)
	{
		g[i].clear();
	}
	return; 
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		init(n);
		for(int i=1;i<=m;i++)
		{
			char xa,xb;
			int a,b;
			scanf(" %c%d %c%d",&xa,&a,&xb,&b);
			bool pa=(xa=='m'),pb=(xb=='m');
	        g[a+n*(pa&1)].push_back(b+n*(pb^1));
	        g[b+n*(pb&1)].push_back(a+n*(pa^1));      
		}
		for(int i=1;i<=(n<<1);i++)
		{
			if(!dfn[i])
				tarjan(i);
		}
		for(int i=1;i<=n;i++)
		{
			if(color[i]==color[i+n])
			{
				puts("BAD");
				return 0;
			}
		}
		puts("GOOD");
	}
	return 0;
}