Pewnego dnia Dong-hyeon, wpatrując się w drzewo, odkrył niezwykły fakt. Okazuje się, że istnieją tylko dwa rodzaje drzew o czterech wierzchołkach: kształt „ㄷ” oraz kształt „ㅈ”!

Dla dowolnego drzewa o co najmniej czterech wierzchołkach wybierzmy zbiór czterech wierzchołków. Jeśli po pozostawieniu tylko krawędzi łączących wierzchołki należące do tego zbioru, te cztery wierzchołki tworzą spójne drzewo, to będzie ono miało kształt „ㄷ” lub „ㅈ”. Niech liczba „ㄷ” oraz liczba „ㅈ” w drzewie oznaczają odpowiednio liczbę zbiorów czterech wierzchołków tworzących kształt „ㄷ” oraz kształt „ㅈ”.

Dong-hyeon podzielił wszystkie drzewa na świecie na trzy rodzaje: Drzewo D: drzewo, w którym liczba „ㄷ” jest większa niż 3-krotność liczby „ㅈ”. Drzewo G: drzewo, w którym liczba „ㄷ” jest mniejsza niż 3-krotność liczby „ㅈ”. * Drzewo DUDUDUNGA: drzewo, w którym liczba „ㄷ” jest dokładnie 3 razy większa od liczby „ㅈ”.

Podekscytowany Dong-hyeon zaczął liczyć „ㄷ” i „ㅈ” w każdym napotkanym drzewie. Jednak wkrótce natknął się na drzewo z 300 000 wierzchołków i stracił zapał. Pomóż Dong-hyeonowi i określ, czy dane drzewo jest drzewem typu D, G, czy DUDUDUNGA!

Wejście

W pierwszej linii podana jest liczba wierzchołków drzewa $N$ ($4 \le N \le 300\,000$). W kolejnych $N-1$ liniach podane są numery dwóch wierzchołków $u, v$ połączonych krawędzią ($1 \le u, v \le N$).

Wyjście

W pierwszej linii wypisz D, jeśli drzewo jest typu D, G, jeśli jest typu G, lub DUDUDUNGA, jeśli jest typu DUDUDUNGA.

Przykład

Wejście 1

4
1 2
2 3
3 4

Wyjście 1

D

Wejście 2

4
1 2
1 3
1 4

Wyjście 2

G

Wejście 3

6
1 2
2 3
3 4
4 5
4 6

Wyjście 3

DUDUDUNGA