Un jour, en observant attentivement un arbre, Dong-hyeon a découvert un fait remarquable : il n'existe que deux types d'arbres à quatre sommets, à savoir la forme « ㄷ » et la forme « ㅈ » !

Pour tout arbre possédant au moins quatre sommets, choisissons un ensemble de quatre sommets. Si, en ne conservant que les arêtes de l'arbre original reliant deux sommets appartenant à cet ensemble, les quatre sommets forment un arbre, alors cet arbre sera soit de forme « ㄷ », soit de forme « ㅈ ». Appelons le nombre de « ㄷ » et le nombre de « ㅈ » dans un arbre le nombre d'ensembles de quatre sommets formant respectivement une forme « ㄷ » et une forme « ㅈ ».

Désormais, Dong-hyeon a classé tous les arbres du monde en trois catégories :

• Arbre-D : un arbre où le nombre de « ㄷ » est supérieur à 3 fois le nombre de « ㅈ ».
• Arbre-G : un arbre où le nombre de « ㄷ » est inférieur à 3 fois le nombre de « ㅈ ».
• Arbre-DUDUDUNGA : un arbre où le nombre de « ㄷ » est exactement égal à 3 fois le nombre de « ㅈ ».

Tout excité, Dong-hyeon a commencé à compter le nombre de « ㄷ » et de « ㅈ » dans chaque arbre qu'il voyait. Cependant, un arbre avec 300 000 sommets s'est bientôt présenté devant lui, et Dong-hyeon a perdu la tête. À sa place, déterminez si l'arbre donné est un Arbre-D, un Arbre-G ou un Arbre-DUDUDUNGA !

Entrée

La première ligne contient le nombre de sommets $N$ de l'arbre. ($4 \le N \le 300\,000$)

À partir de la deuxième ligne, $N-1$ lignes contiennent les numéros $u, v$ des deux sommets reliés par chaque arête de l'arbre. ($1 \le u, v \le N$)

Sortie

Affichez D si l'arbre donné est un Arbre-D, G s'il s'agit d'un Arbre-G, et DUDUDUNGA s'il s'agit d'un Arbre-DUDUDUNGA.

Exemples

Entrée 1

4
1 2
2 3
3 4

Sortie 1

D

Entrée 2

4
1 2
1 3
1 4

Sortie 2

G

Entrée 3

6
1 2
2 3
3 4
4 5
4 6

Sortie 3

DUDUDUNGA

Figure 1. Les deux types d'arbres à quatre sommets : la forme « ㄷ » (à gauche) et la forme « ㅈ » (à droite).