#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<iostream>
#define Pair pair<int,int>
#define F first
#define S second
using namespace std;
const int MAXN=1e6+10;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{ char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct node
{
int u,v,nxt;
}edge[MAXN];
int head[MAXN],num=1;
int dfn[MAXN],low[MAXN],tot=0,color[MAXN],vis[MAXN],colornum=0;
stack<int>s;
inline void AddEdge(int x,int y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].nxt=head[x];
head[x]=num++;
}
void tarjan(int now)
{
dfn[now]=low[now]=++tot;
s.push(now);
vis[now]=1;
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(!dfn[edge[i].v]) tarjan(edge[i].v),low[now]=min(low[now],low[edge[i].v]);
else if(vis[edge[i].v]) low[now]=min(low[now],dfn[edge[i].v]);
}
if(dfn[now]==low[now])
{
int h;colornum++;
do
{
h=s.top();s.pop();
vis[h]=0;
color[h]=colornum;
}while(h!=now);
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int QWQ=read();
while(QWQ--)
{
int N=read(),M=read();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
num=1;
int a,b;char x,y,temp;
for(int i=1;i<=M;i++)
{
while(x!='m'&&x!='h') x=getchar();
a=read();
while(y!='m'&&y!='h') y=getchar();
b=read();
if(x=='m')
if(y=='h') AddEdge(a+N,b+N),AddEdge(b,a);
else AddEdge(a+N,b),AddEdge(b+N,a);
else
if(y=='h') AddEdge(a,b+N),AddEdge(b,a+N);
else AddEdge(a,b),AddEdge(b+N,a+N);
x='0';y='0';
}
for(int i=1;i<=2*N;i++)
if(!dfn[i]) tarjan(i);
bool flag=1;
for(int i=1;i<=N;i++)
if(color[i]==color[i+N])
{printf("BAD\n");flag=0;break;}
if(flag==1) printf("GOOD\n");
}
return 0;
}
网友评论