ある日、木をじっと眺めていたドンヒョンは、驚くべき事実を発見した。頂点が4つある木は、「ㄷ」型と「ㅈ」型の2種類しかないという事実である！

頂点が4つ以上ある任意の木について、その木から頂点を4つ選ぶ集合を考える。木全体の辺のうち、集合に含まれる2つの頂点を結ぶ辺だけを残したとき、4つの頂点が1つの木としてつながるならば、それは「ㄷ」型か「ㅈ」型のいずれかである。木における「ㄷ」の個数と「ㅈ」の個数を、それぞれ木の中で「ㄷ」型、「ㅈ」型をなす4つの頂点の集合の個数と定義する。

さて、ドンヒョンは世の中のすべての木を次のような3種類に分類した。

• D-木：「ㄷ」の個数が「ㅈ」の個数の3倍より多い木
• G-木：「ㄷ」の個数が「ㅈ」の個数の3倍より少ない木
• DUDUDUNGA-木：「ㄷ」の個数が「ㅈ」の個数のちょうど3倍である木

大喜びしたドンヒョンは、木を見るたびにその木に含まれる「ㄷ」と「ㅈ」の個数を数え始めた。しかし、すぐに頂点が30万個もある木がドンヒョンの前に現れ、ドンヒョンは気を失ってしまった。ドンヒョンに代わって、与えられた木がD-木なのか、G-木なのか、それともDUDUDUNGA-木なのかを教えてあげよう！

入力

1行目に木の頂点数 $N$ が与えられる。 ($4 \le N \le 300\,000$)

2行目から $N-1$ 行にわたって、木の各辺が結ぶ2つの頂点の番号 $u, v$ が与えられる。 ($1 \le u, v \le N$)

出力

1行目に、与えられた木が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

Figure 1. 「ㄷ」型と「ㅈ」型の構造