One day, while staring blankly at a tree, Dong-hyeon discovered a remarkable fact. It is that there are only two types of trees with four vertices: the 'ㄷ' shape and the 'ㅈ' shape!

For any tree with four or more vertices, let us choose a set of four vertices. If we keep only the edges of the original tree that connect two vertices within this set, and these four vertices form a single connected tree, it will be either a 'ㄷ' shape or a 'ㅈ' shape. Let the number of 'ㄷ' shapes and 'ㅈ' shapes in a tree be the number of such sets of four vertices that form a 'ㄷ' shape and a 'ㅈ' shape, respectively.

Now, Dong-hyeon has classified all trees in the world into the following three types:

• D-tree: A tree where the number of 'ㄷ' shapes is greater than 3 times the number of 'ㅈ' shapes.
• G-tree: A tree where the number of 'ㄷ' shapes is less than 3 times the number of 'ㅈ' shapes.
• DUDUDUNGA-tree: A tree where the number of 'ㄷ' shapes is exactly 3 times the number of 'ㅈ' shapes.

Excited, Dong-hyeon started counting the number of 'ㄷ' and 'ㅈ' shapes in every tree he saw. However, he soon encountered a tree with 300,000 vertices and lost his mind. Let's help Dong-hyeon determine whether a given tree is a D-tree, a G-tree, or a DUDUDUNGA-tree!

Input

The first line contains the number of vertices $N$ in the tree. ($4 \le N \le 300\,000$)

From the second line, $N-1$ lines follow, each containing two vertex numbers $u$ and $v$ connected by an edge. ($1 \le u, v \le N$)

Output

If the given tree is a D-tree, print D; if it is a G-tree, print G; if it is a DUDUDUNGA-tree, print DUDUDUNGA.

Examples

Input 1

4
1 2
2 3
3 4

Output 1

D

Input 2

4
1 2
1 3
1 4

Output 2

G

Input 3

6
1 2
2 3
3 4
4 5
4 6

Output 3

DUDUDUNGA

Figure 1. The two types of trees with four vertices: the 'ㄷ' shape (left) and the 'ㅈ' shape (right).