#819. [2-SAT模板题][JSOI2010] 满汉全席

[2-SAT模板题][JSOI2010] 满汉全席

[JSOI2010] 满汉全席

题目描述

满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在数量繁多的菜色之中。由于菜色众多而繁杂,只有极少数博学多闻技艺高超的厨师能够做出满汉全席,而能够烹饪出经过专家认证的满汉全席,也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成,而他们之间还细分为许多不同等级的厨师。

为了招收新进的厨师进入世界满汉全席协会,将于近日举办满汉全席大赛,协会派遣许多会员当作评审员,为的就是要在参赛的厨师之中,找到满汉界的明日之星。

大会的规则如下:每位参赛的选手可以得到 nn 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是:共有 mm 位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解,但基本见解是,要有两样菜色作为满汉全席的标志。如某评审认为,如果没有汉式东坡肉跟满式的涮羊肉锅,就不能算是满汉全席。但避免过于有主见的审核,大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下,才能淘汰一位选手,否则不能淘汰一位选手。

换句话说,只要参赛者能在这两种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉,羊肉和牛肉时,有四位评审员的喜好如下表:

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

如参赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而参赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理,就可以满足所有评审的要求。

但大会后来发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的参赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。

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

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

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

输入格式

第一行包含一个数字 KK1K501\le K \le 50),代表测试文件包含了 KK 组数据。

每一组测试数据的第一行包含两个数字 nnmmn100n≤100m1000m≤1000),代表有 nn 种材料,mm 位评审员。

为方便起见,舍弃做法的中文名称而给予编号,编号分别从 11nn

接下来的 mm 行,每行都代表对应的评审员所拥有的两个喜好,每个喜好由一个英文字母跟一个数字代表,如 m1m1 代表这个评审喜欢第 11 个材料透过满式料理做出来的菜,而 h2h2 代表这个评审员喜欢第 22 个材料透过汉式料理做出来的菜。

输出格式

每组测试数据输出一行,如果不会发生没有人能通过考核的窘境,输出 GOOD;否则输出 BAD(均为大写字母)。

样例 #1

样例输入 #1

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

样例输出 #1

GOOD
BAD