Description

The Manchu-Han Banquet is the most lavish Chinese banquet. Many different ingredients, cooked in either Manchu or Han style, appear as a large variety of dishes. Because it is so complex, only a few highly skilled and knowledgeable chefs can make a Manchu-Han Banquet. Being able to cook a Manchu-Han Banquet certified by experts is one of the greatest honors for a Chinese chef. The World Manchu-Han Banquet Association consists of expert chefs capable of cooking this banquet, and they are further divided into different ranks.

To recruit new chefs into the association, a Manchu-Han Banquet competition will be held soon. The association will send many members to serve as judges, aiming to find the rising star among the contestants.

The rules are as follows: each contestant receives $n$ types of ingredients and can freely choose to cook each ingredient in Manchu style or Han style.

The judging system is: there are $m$ judges in total. Each judge has a unique view of the banquet, but the basic idea is that there are two hallmark dishes. For example, a judge may think that without Han-style braised pork (Dongpo pork) and Manchu-style mutton hotpot, it cannot be called a Manchu-Han Banquet. To avoid overly subjective judging, the contest rules state that a judge can eliminate a contestant only if both of their required dishes are missing; otherwise, the judge may not eliminate the contestant.

In other words, as long as the contestant’s choice for at least one of the two specified ingredients matches the judge’s preference, the contestant passes that judge. For example, if the ingredients are pork, mutton, and beef, and four judges have the following preferences:

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

If contestant A cooks Manchu-style pork, Manchu-style mutton, and Manchu-style beef, they cannot satisfy judge three and thus fail that judge. If contestant B cooks Han-style pork, Manchu-style mutton, and Manchu-style beef, they satisfy all judges.

However, the organizers later found that under such a system, if the choice of ingredients and the set of judges are not suitably arranged, all contestants might pass at most part of the judges rather than all of them, so no one could pass the entire evaluation.

For example, if four judges have the following preferences, then no matter what choices a contestant makes, it is impossible to satisfy all judges:

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

Therefore, the organizers hope for a program to determine whether the selected $m$ judges will lead to the awkward situation where no one can pass the evaluation, so that the association can form a suitable judging panel.

Input Format

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

For each test case, the first line contains two integers $n$ and $m$ ($n≤100$, $m≤1000$), meaning there are $n$ types of ingredients and $m$ judges.

For convenience, we discard the Chinese names and assign IDs from $1$ to $n$.

The next $m$ lines each describe the two preferences of a judge. Each preference is represented by an English letter and a number. For example, $m1$ means this judge likes ingredient $1$ cooked in Manchu style, and $h2$ means this judge likes ingredient $2$ cooked in Han style.

Output Format

For each test case, output one line. If it will not happen that nobody can pass the evaluation, output GOOD; otherwise output BAD (uppercase letters).

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

GOOD
BAD

Hint

Translated by ChatGPT 5