the first 2 sat
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<stack> using namespace std; const int N=205; int n,m; int head[N],to[N*N],pre[N*N],tot; void addedge(int u,int v) {to[++tot]=v;pre[tot]=head[u];head[u]=tot;} int num(char *ch) { int len=strlen(ch),ans=0; for (int i=1;i<len;i++) ans=ans*10+ch[i]-'0'; return ans; } int rev(int num) { if (num>n) return num-n; return num+n; } int dfn[N],low[N],tt,pos[N]; int in[N],ss; stack<int> s; void dfs(int u) { low[u]=dfn[u]=++tt; in[u]=1; s.push(u); for (int i=head[u];i;i=pre[i]) if (!dfn[to[i]]) { dfs(to[i]); low[u]=min(low[u],low[to[i]]); }else if (in[to[i]]==1) low[u]=min(low[u],dfn[to[i]]); if (dfn[u]==low[u]) { int v; ss++; do { v=s.top();s.pop(); in[v]=2;pos[v]=ss; }while (v!=u); } } void work() { memset(head,0,sizeof(head));tot=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low));tt=0; memset(in,0,sizeof(in));ss=0; memset(pos,0,sizeof(pos)); scanf("%d%d",&n,&m); char ch[7]; int num1,num2; for (int i=1;i<=m;i++) { scanf("%s",ch); num1=num(ch);if (ch[0]=='h') num1+=n; scanf("%s",ch); num2=num(ch);if (ch[0]=='h') num2+=n; addedge(rev(num1),num2); addedge(rev(num2),num1); } for (int i=1;i<=n*2;i++) if (!dfn[i]) dfs(i); bool o=true; for (int i=1;i<=n;i++) if (pos[i]==pos[i+n]) o=false; if (o) printf("GOOD\n"); else printf("BAD\n"); } int main() { int T; scanf("%d",&T); while (T--) work(); return 0; }