C. 三子棋

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

果果和岚岚是两只聪明的小猪,她们经常在纸上玩一个叫做三子棋的游戏。三子棋指的是两猪轮流在一个的方格棋盘中落子,先手执黑、后手执白。如果有任意一个回合,某一行、列、对角线上的个棋子 同时 为黑或者为白则游戏立刻结束,黑方或白方 获胜。

渐渐地,果果和岚岚不再满足于在普通的方格棋盘上下棋,她们会去收集各种各样奇怪的棋盘。这些棋盘都有 个格子,岚岚是一只认真的小猪,她总是喜欢把 条格子之间的相邻关系记在自己的小本本上,并找到了两条规律:相邻关系不会超过 条;且这些相邻关系可以保证棋盘不会断开 (输入保证棋盘连通)

其中,对获胜的定义为:若存在格子 与格子 相邻,且格子 与格子 相邻。某一个回合后, 三个格子同时落下黑子或白子,则宣告游戏结束,黑方或白方 获胜。

而对平局的定义为:直至整个棋盘的每个格子都被落了子,获胜的情况仍然没有发生。

需要补充说明的是,果果和岚岚保证和谐友好地进行游戏, 即她们不会去修改对方已经下好的棋子

果果和岚岚是两只聪明绝顶的小猪,假设她们总是会做出正确的决策且 果果执黑子 。请你对着岚岚的小本本编写一个程序,试判断这场游戏 由谁获胜 或者是 平局

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 ,表示数据组数。

接下来包含 组数据,每组数据的格式如下:

第一行包含两个整数 ,分别表示格子的个数和相邻关系的数量。

接下来 行,每行包含两个正整数 ,表示编号为 的格子与编号为 的格子是相邻的,编号保证为

输出格式

对于每组数据:输出一行,若果果获胜,则输出大写字母 ;若岚岚获胜,则输出大写字母 ;若平局,则输出大写字母

样例

样例输入 1

2
5 4
1 2
2 3
2 4
2 5
4 3
1 2
1 3
1 4

样例输出 1

G
D

第一组数据中:果果在点落子;岚岚在点落子;果果在点落子;岚岚在点落子;果果在点落子,此时形成三子,果果胜。
第二组数据中:果果只能落下子,必然平局。

数据范围与提示

对于所有测试数据,保证: ,
| 测试点 | |特殊性质 |
| --- | --- | --- |
| | | 无 |
| | | 数据随机生成 |
| | | 无 |