TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2096
  • 题目
  • P2096【JSOI2010】满汉全席
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    为了招收新进的厨师进入世界满汉全席协会,将于近日举办满汉全席大赛,协会派出许多会员当作评委,为的就是要在参赛的厨师之中,找到满汉料理界的明日之星。 每位参赛的选手可以得到 n 种材料,选手可以自由选择用满式或是汉式料理将材料做成菜肴。

    大赛共有 m 位评委把关。每一位评委对于满汉全席有各自独特的见解,但基本的见解是:要有两样菜色作为满汉全席的标志。如某评委认为,如果没有汉式东坡肉及满式的涮羊肉锅,就不能算是满汉全席。 为了避免过于有主见的评审意见,大会规定,对每一位参赛者来说,一个评委除非是在认为必备的两样菜色都没有做出来的状况下,才能淘汰他,否则就不能淘汰他。换句话说,参赛者在这两种材料的做法中,只要其中一个能符合评委的喜好,即可通过该评委的审查。例如,当材料中有猪肉、羊肉和牛肉时,有四位评委的喜好如下表所示

    评审一     评审二     评审三     评审四
    满式牛肉   满式猪肉   汉式牛肉   汉式牛肉
    汉式猪肉   满式羊肉   汉式猪肉   满式羊肉
    如参赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而参赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理,就可以满足所有评审的要求。
    但大会后来发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的参赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时,则不论参赛者采取什么样的做法,都不可能通过所有评审的考核:
    评审一     评审二     评审三     评审四
    满式羊肉   满式猪肉   汉式羊肉   汉式羊肉
    汉式猪肉   满式羊肉   汉式猪肉   满式猪肉
    所以大会希望有人能写一个程序来判断,所选出的𝑚 位评审,会不会发生没有人能通过考核的窘境,以便协会组织合适的评审团。
    

    输入格式

    第一行包含一个数字 K,代表测试文件包含了K 组测试数据。
    每一组测试数据的第一行包含两个数字n 和m(n≤100,m≤1000),代表有n 种材料,m 位评委。
    为方便起见,材料舍弃中文名称而给予编号,编号分别从1 到n。
    接下来的m 行,每行都代表对应的评委所拥有的两个喜好,每个喜好由一个英文字母和一个数字代表,如m1 代表这个评委喜欢第 1 种材料通过满式料理做出来的菜,而h2 代表这个评委喜欢第 2 种材料通过汉式料理做出来的菜。
    每个测试文件不会有超过 50 组的测试数据。

    输出格式

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

    样例输入

    输入样例1:
    2
    3 3
    h1 m3
    h3 m2
    m3 m1
    3 3
    h1 m2
    h2 m3
    h3 m1
    输入样例2:

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

    样例输出

    输出样例1:
    GOOD
    GOOD
    输出样例2:
    GOOD 
    BAD 

    提示

    对于100%的数据,n≤15,m≤100,k≤50


    来源  HZOI