有一天，東賢盯著樹看時，發現了一個驚人的事實。那就是，頂點數為四的樹只有「ㄷ」型和「ㅈ」型這兩種！

對於任意頂點數大於等於四的樹，我們從中選出一個由四個頂點組成的集合。若僅保留原樹中連接該集合內兩個頂點的邊，且這四個頂點能連成一個樹狀結構，那麼它必然是「ㄷ」型或「ㅈ」型。我們將樹中「ㄷ」型的數量與「ㅈ」型的數量，分別定義為該樹中構成「ㄷ」型與「ㅈ」型結構的四頂點集合的個數。

現在，東賢將世上所有的樹分為以下三類：

• 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