Description

满汉全席是中国最丰盛的宴客菜肴, 有许多种不同的材料透过满族或是汉族的料理方式, 呈现在數量繁多的菜色之中. 由于菜色众多而繁杂, 只有极少數博学多闻技艺高超的厨师能够做出满汉全席, 而能够烹饪出经过专家认证的满汉全席, 也是中国厨师最大的荣誉之一. 世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成, 而他们之间还细分为许多不同等级的厨师. 为了招收新进的厨师进入世界满汉全席协会, 将于近日举办满汉全席大赛, 协会派遣许多会员当作评审员, 为的就是要在參赛的厨师之中, 找到满汉料理界的明日之星.

大会的规则如下: 每位參赛的选手可以得到 \(n\) 种材料, 选手可以自由选择用满式或是汉式料理将材料当成菜肴. 大会的评审制度是: 共有 \(m\) 位评审员分别把关. 每一位评审员对于满汉全席有各自独特的見解, 但基本见解是, 要有兩样菜色作为满汉全席的标志. 如某评审认为, 如果没有汉式东坡肉跟满式的涮羊肉锅, 就不能算是满汉全席. 但避免过于有主見的审核, 大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下, 才能淘汰一位选手, 否则不能淘汰一位參赛者. 换句话說, 只要參赛者能在这兩种材料的做法中, 其中一个符合评审的喜好即可通过该评审的审查. 如材料有猪肉, 羊肉和牛肉时, 有四位评审员的喜好如下表:

评审一 评审二 评审三 评审四
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉

如參赛者甲做出满式猪肉, 满式羊肉和满式牛肉料理, 他将无法满足评审三的要求, 无法通过评审. 而參赛者乙做出汉式猪肉, 满式羊肉和满式牛肉料理, 就可以满足所有评审的要求. 但大会后來发现, 在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话, 所有的參赛者最多只能通过部分评审员的审查而不是全部, 所以可能会发生没有人通过考核的情形.

如有四个评审员喜好如下表时, 则不論參赛者采取什么样的做法, 都不可能通过所有评审的考核:

评审一 评审二 评审三 评审四
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉

所以大会希望有人能写一个程序判断, 所选出的 \(m\) 位评审, 会不会发生没有人能通过考核的窘境, 以便协会组织合适的评审团.

Input

第一行包含一个数字 \(k\), 代表测试文件包含了 \(k\) 组资料.

每一组测试资料的第一行包含兩个数字 \(n, m\), 代表有 \(n\) 种材料,\(m\) 位评审员. 为方便起見, 材料舍弃中文名称而给予编号, 编号分别从 \(1\) 到 \(n\).

接下來的 \(m\) 行, 每行都代表对应的评审员所拥有的兩个喜好, 每个喜好由一个英文字母跟一个数字代表, 如 \(m1\) 代表这个评审喜欢第 \(1\) 个材料透过满式料理做出來的菜, 而 \(h2\) 代表这个评审员喜欢第 \(2\) 个材料透过汉式料理做出來的菜.

Output

每组测试资料输出一行, 如果不会发生没有人能通过考核的窘境, 输出 GOOD; 否则输出 BAD.

Sample Input

2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2

Sample Output

GOOD
BAD

Data Range

对于所有的数据, 满足:\(k \leq 50, 1 \leq n \leq 100, 1 \leq m \leq 1000\).

Explanation

首先这个 scanf 实在无力吐嘈----读字符是最烦人的......

对于一个评审员, 其要求的两种食材分别为 \(a, b\), 对应地满汉式分别为 \(x, y\), 其中 \(0 \leq x, y \leq 1\). 考虑将每一种食材拆点, 为 \(2a - 1, 2a\), 然后两种菜肴如果被一个评审员同时要求, 则连一条双向边.

最后跑一个强连通分量缩点. 如果一种食材的两种菜肴在一个强连通分量中, 则这个评审员方案是不好的.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 50010;

class Tarjan
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, ecnt, dcnt, bcnt;
    edge *edges[maxn], epool[maxm];
    int low[maxn], dfn[maxn], belong[maxn];
    bool instk[maxn];
    stack<int> stk;
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    void dfs(int p)
    {
        low[p] = dfn[p] = ++dcnt;
        stk.push(p); instk[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            int q = ep->v;
            if (!dfn[q]) {
                dfs(q);
                if (low[q] < low[p])
                    low[p] = low[q];
            } else {
                if (instk[q] && dfn[q] < low[p])
                    low[p] = dfn[q];
            }
        }
        if (low[p] == dfn[p]) {
            int q = 0;
            bcnt += 1;
            do {
                q = stk.top();
                stk.pop(); instk[q] = false;
                belong[q] = bcnt;
            } while (q != p);
        }
        return ;
    }
    void clear(void)
    {
        n = ecnt = dcnt = bcnt = 0;
        memset(edges, 0, sizeof(edges));
        return ;
    }
    void eval(void)
    {
        memset(dfn, 0, sizeof(dfn));
        memset(instk, 0, sizeof(instk));
        while (!stk.empty())
            stk.pop();
        for (int i = 2; i <= n; i++)
            if (!dfn[i])
                dfs(i);
        return ;
    }
    bool judge(void)
    {
        for (int i = 2; i <= n; i += 2)
            if (belong[i] == belong[i + 1])
                return false;
        return true;
    }
} graph;

int T, n, m;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        // Downvote this input
        scanf("%d%d", &n, &m);
        char ch1, ch2;
        graph.clear();
        for (int i = 1, a, b; i <= m; i++) {
            scanf("\n%c%d %c%d", &ch1, &a, &ch2, &b);
            int p1 = 2 * a + (ch1 == 'h'),
                p2 = 2 * b + (ch2 == 'h');
            graph.add_edge(p1^1, p2);
            graph.add_edge(p2^1, p1);
        }
        // Get the result done
        graph.n = 2 * n + 1;
        graph.eval();
        // Judge this
        printf("%s\n", graph.judge() ? "GOOD" : "BAD");
    }
    return 0;
}