The Man-Han Feast

Problem Source

JSOI2010

Problem Description

The Man-Han Feast is the most sumptuous banquet in Chinese cuisine, with many different ingredients prepared in either Man or Han style, presented in a great variety of dishes. Because of the sheer number of dishes, only a handful of extraordinarily learned and skilled chefs can cook the Man-Han Feast, and being certified by experts as able to cook it is one of the greatest honours for a Chinese chef. The World Man-Han Feast Association is composed of expert chefs who can cook the Man-Han Feast, and they are further divided into many grades of chefs.

To recruit new chefs into the association, a Man-Han Feast contest will be held soon. The association sends many members as judges, in order to find the rising star of the Man-Han world among the contestants.

The rules of the contest are as follows: each contestant is given $n$ kinds of ingredients and may freely choose to cook each ingredient either in Man style or in Han style.

The judging system: there are $m$ judges, each acting independently. Every judge has his own unique opinion about the Man-Han Feast, but the basic idea is that two dishes must serve as the signature of the feast. For example, one judge may think that without Han-style Dongpo pork and Man-style mutton hotpot, it cannot be called a Man-Han Feast. To avoid overly opinionated judging, the contest rules state that a judge may eliminate a contestant only when NEITHER of his two required dishes is made; otherwise the contestant must pass that judge's review.

In other words, a contestant passes a judge's review as long as at least one of the two ingredients is cooked in the way that judge likes. For instance, with ingredients pork, mutton and beef, and four judges with preferences as in the table below:

Judge 1   Judge 2    Judge 3    Judge 4
Man beef  Man pork   Han beef   Han beef
Han pork  Man mutton Han pork   Man mutton

If contestant A cooks Man-style pork, Man-style mutton and Man-style beef, he fails to satisfy Judge 3 and cannot pass. But if contestant B cooks Han-style pork, Man-style mutton and Man-style beef, he satisfies all judges.

However, the association later found that under this system, if the ingredient choices and the dispatched judges are not specially arranged, all contestants can at best pass only some judges rather than all of them, so it is possible that no one passes the assessment.

For example, with four judges whose preferences are as in the table below, no matter what a contestant does, it is impossible to pass all judges:

Judge 1    Judge 2    Judge 3    Judge 4
Man mutton Man pork   Han mutton Han mutton
Han pork   Man mutton Han pork   Man pork

So the association wants a program to decide, for the selected $m$ judges, whether it is possible that no contestant can pass the assessment, so that they can organize a suitable panel of judges.

Input Format

The first line contains one number $K\ (1 \le K \le 50)$, meaning the test file contains $K$ test cases.

For each test case, the first line contains two numbers $n$ and $m\ (n \le 100,\ m \le 1000)$, meaning there are $n$ kinds of ingredients and $m$ judges.

For convenience, the Chinese names of the cooking styles are dropped and replaced by numbers, numbered from $1$ to $n$.

The next $m$ lines each describe the two preferences of the corresponding judge. Each preference is represented by one English letter and one number, e.g. m1 means this judge likes ingredient $1$ cooked in Man style, while h2 means this judge likes ingredient $2$ cooked in Han style.

Output Format

For each test case output one line: if it is impossible that no contestant can pass the assessment (i.e. there exists a contestant who passes all judges), output GOOD; otherwise output BAD (both in uppercase).

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