[JSOI 2010] 满汉全席

#include<bits/stdc++.h>using namespace std;#define MAXN 110#define MAXM 1010struct edge{ ???????int to,nxt;} e[MAXM << 1];int timer,cnt,top,tot;int dfn[MAXN << 1],low[MAXN << 1],belong[MAXN << 1],s[MAXN << 1],head[MAXN << 1];bool instack[MAXN];template <typename T> inline void read(T &x){ ???????int f = 1; x = 0; ???????char c = getchar(); ???????for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; ???????for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; ???????x *= f;}inline void addedge(int u,int v){ ???????tot++; ???????e[tot] = (edge){v,head[u]}; ???????head[u] = tot; }inline void tarjan(int u){ ???????low[u] = dfn[u] = ++timer; ???????instack[u] = true; ???????s[++top] = u; ???????for (int i = head[u]; i; i = e[i].nxt) ???????{ ???????????????int v = e[i].to; ???????????????if (!dfn[v]) ???????????????{ ???????????????????????tarjan(v); ???????????????????????low[u] = min(low[u],low[v]); ???????????????} else if (instack[v]) low[u] = min(low[u],dfn[v]); ???????} ???????if (low[u] == dfn[u]) ???????{ ???????????????cnt++; ???????????????while (s[top + 1] != u) ???????????????{ ???????????????????????instack[s[top]] = false; ???????????????????????belong[s[top]] = cnt; ???????????????????????top--; ???????????????} ???????}}int main() { ???????????????int T; ???????read(T); ???????while (T--) ???????????????{ ???????????????int n,m; ???????????????read(n); read(m); ???????????????tot = 0; ???????????????for (int i = 1; i <= 2 * n; i++) head[i] = 0; ???????????????for (int i = 1; i <= m; i++) ???????????????{ ???????????????????????char a[20] , b[20]; ???????????????????????scanf("%s%s",a + 1,b + 1); ???????????????????????int t1 = 0 , t2 = 0; ???????????????????????for (int j = 2; j <= strlen(a + 1); j++) t1 = t1 * 10 + a[j] - ‘0‘; ???????????????????????for (int j = 2; j <= strlen(b + 1); j++) t2 = t2 * 10 + b[j] - ‘0‘; ???????????????????????if (a[1] == ‘m‘) addedge(t1 + n,t2 + (b[1] == ‘h‘) * n); ???????????????????????else addedge(t1,t2 + (b[1] == ‘h‘) * n); ???????????????????????if (b[1] == ‘m‘) addedge(t2 + n,t1 + (a[1] == ‘h‘) * n); ???????????????????????else addedge(t2,t1 + (a[1] == ‘h‘) * n); ???????????????} ????????????????timer = cnt = 0; ???????????????for (int i = 1; i <= 2 * n; i++) low[i] = dfn[i] = 0; ???????????????for (int i = 1; i <= 2 * n; i++) ???????????????{ ???????????????????????if (!dfn[i]) ???????????????????????????????tarjan(i); ???????????????} ???????????????bool ans = true; ???????????????for (int i = 1; i <= n; i++) ???????????????{ ?????????????????????if (belong[i] == belong[i + n]) ??????????????????????{ ?????????????????????????????ans = false; ?????????????????????????????break; ???????????????????????} ???????????????} ???????????????if (ans) printf("GOOD\n"); ???????????????else printf("BAD\n"); ???????} ???????????????return 0; ???}