Un día, mientras observaba un árbol, Dong-hyeon descubrió un hecho sorprendente: ¡solo existen dos tipos de árboles con cuatro vértices, los cuales tienen forma de ‘ㄷ’ y ‘ㅈ’!

Para cualquier árbol con cuatro o más vértices, elijamos un conjunto de cuatro vértices. Si al dejar solo las aristas del árbol original que conectan a dos vértices dentro de este conjunto, los cuatro vértices forman un árbol, entonces este tendrá forma de ‘ㄷ’ o de ‘ㅈ’. Definamos el número de ‘ㄷ’ y el número de ‘ㅈ’ en un árbol como la cantidad de conjuntos de cuatro vértices que forman una estructura de tipo ‘ㄷ’ o ‘ㅈ’, respectivamente.

Ahora, Dong-hyeon ha clasificado todos los árboles del mundo en tres tipos:

• Árbol-D: Un árbol donde el número de ‘ㄷ’ es mayor que 3 veces el número de ‘ㅈ’.
• Árbol-G: Un árbol donde el número de ‘ㄷ’ es menor que 3 veces el número de ‘ㅈ’.
• Árbol-DUDUDUNGA: Un árbol donde el número de ‘ㄷ’ es exactamente 3 veces el número de ‘ㅈ’.

Emocionado, Dong-hyeon comenzó a contar cuántos ‘ㄷ’ y ‘ㅈ’ había en cada árbol que veía. Sin embargo, pronto apareció ante él un árbol con 300,000 vértices y Dong-hyeon perdió la razón. ¡Ayudemos a Dong-hyeon a determinar si el árbol dado es un Árbol-D, un Árbol-G o un Árbol-DUDUDUNGA!

Entrada

La primera línea contiene el número de vértices del árbol, $N$. ($4 \le N \le 300\,000$)

Desde la segunda línea, se proporcionan $N-1$ líneas, cada una con los números de los dos vértices $u, v$ que conecta cada arista del árbol. ($1 \le u, v \le N$)

Salida

Si el árbol dado es un Árbol-D, imprima D; si es un Árbol-G, imprima G; y si es un Árbol-DUDUDUNGA, imprima DUDUDUNGA.

Ejemplos

Entrada 1

4
1 2
2 3
3 4

Salida 1

D

Entrada 2

4
1 2
1 3
1 4

Salida 2

G

Entrada 3

6
1 2
2 3
3 4
4 5
4 6

Salida 3

DUDUDUNGA

Figura 1. Representación de los árboles con cuatro vértices en forma de ‘ㄷ’ (izquierda) y ‘ㅈ’ (derecha).