有一天，东贤盯着一棵树看，发现了一个惊人的事实：只有四个顶点的树只有“ㄷ”型和“ㅈ”型两种！

对于任意一棵拥有四个或更多顶点的树，我们从中选取一个包含四个顶点的集合。如果我们只保留原树中连接该集合内两个顶点的边，且这四个顶点构成了一棵树，那么它要么是“ㄷ”型，要么是“ㅈ”型。我们将树中“ㄷ”型的数量和“ㅈ”型的数量分别定义为树中构成“ㄷ”型和“ㅈ”型的四个顶点集合的个数。

现在，东贤将世上所有的树分成了以下三类：

• D-树：‘ㄷ’的数量大于‘ㅈ’数量的 3 倍。
• G-树：‘ㄷ’的数量小于‘ㅈ’数量的 3 倍。
• DUDUDUNGA-树：‘ㄷ’的数量恰好是‘ㅈ’数量的 3 倍。

兴奋的东贤一看到树就开始数其中的‘ㄷ’和‘ㅈ’。但很快，一棵拥有 30 万个顶点的树出现在他面前，东贤彻底崩溃了。请代替东贤判断给定的树是 D-树、G-树还是 DUDUDUNGA-树！

输入格式

第一行输入树的顶点数 $N$。($4 \le N \le 300\,000$)

从第二行开始的 $N-1$ 行，每行输入树中每条边连接的两个顶点编号 $u, v$。($1 \le u, v \le N$)

输出格式

如果给定的树是 D-树，则输出 D；如果是 G-树，则输出 G；如果是 DUDUDUNGA-树，则输出 DUDUDUNGA。

样例

输入 1

4
1 2
2 3
3 4

输出 1

D

输入 2

4
1 2
1 3
1 4

输出 2

G

输入 3

6
1 2
2 3
3 4
4 5
4 6

输出 3

DUDUDUNGA