Luogu P4171 [JSOI2010]满汉全席

题目链接：​​传送门​​

2-sat板子题
注意输入的时候可不要以为w和h后面数字只有一位

 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A];
int head[A], num;
void add(int fr, int to) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
int dfn[A], low[A], sta[A], cnt, top, kn, vis[A], bl[A];
int n, m, a, b, x, y, T;
void tarjan(int fr) {
    dfn[fr] = low[fr] = ++cnt, sta[++top] = fr, vis[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (!dfn[ca]) tarjan(ca), low[fr] = min(low[fr], low[ca]);
        else if (vis[ca]) low[fr] = min(low[fr], dfn[ca]);
    }
    if (low[fr] == dfn[fr]) {
        int p; kn++;
        do {
            p = sta[top--];
            vis[p] = 0;
            bl[p] = kn;
        }while (p != fr);
    }
}

int main(int argc, char const *argv[]) {
    cin >> T;
    while (T--) {
        memset(vis, 0, sizeof vis);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(head, 0, sizeof head);
        kn = cnt = top = num = 0;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            char s1 = getchar();
            while (s1 != 'm' and s1 != 'h') s1 = getchar();
            x = s1 == 'm' ? 1 : 0; cin >> a;
            char s2 = getchar();
            while (s2 != 'm' and s2 != 'h') s2 = getchar();
            y = s2 == 'm' ? 1 : 0; cin >> b;
            add(a + n * x, b + n * (y ^ 1));
            add(b + n * y, a + n * (x ^ 1));
        }
        for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) tarjan(i);
        for (int i = 1; i <= n; i++) if (bl[i] == bl[i + n]) {puts("BAD"); goto portal;}
        puts("GOOD"); portal:;
    }
}