Однажды Донхён, задумчиво глядя на дерево, сделал удивительное открытие. Оказывается, существует всего два типа деревьев с четырьмя вершинами: «ㄷ» и «ㅈ»!

Для любого дерева, содержащего не менее четырех вершин, выберем подмножество из четырех вершин. Если оставить только те ребра исходного дерева, которые соединяют вершины из этого подмножества, и в результате эти четыре вершины образуют связное дерево, то оно будет иметь либо форму «ㄷ», либо форму «ㅈ». Обозначим количество «ㄷ» и «ㅈ» в дереве как количество подмножеств из четырех вершин, образующих соответствующие формы.

Теперь Донхён разделил все деревья в мире на три типа:

• D-дерево: количество «ㄷ» больше, чем количество «ㅈ», умноженное на 3.
• G-дерево: количество «ㄷ» меньше, чем количество «ㅈ», умноженное на 3.
• DUDUDUNGA-дерево: количество «ㄷ» ровно в 3 раза больше количества «ㅈ».

Обрадованный Донхён начал считать количество «ㄷ» и «ㅈ» в каждом встреченном им дереве. Однако вскоре ему попалось дерево с 300 000 вершин, и он потерял самообладание. Помогите Донхёну определить, является ли заданное дерево D-деревом, G-деревом или DUDUDUNGA-деревом!

Входные данные

В первой строке задано количество вершин дерева $N$ ($4 \le N \le 300\,000$). Начиная со второй строки, заданы $N-1$ строк, каждая из которых содержит два целых числа $u$ и $v$, обозначающих ребро между вершинами $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

Формы «ㄷ» и «ㅈ»