Một ngày nọ, khi đang chăm chú nhìn vào một cái cây, Dong-hyeon đã phát hiện ra một sự thật đáng kinh ngạc. Đó là, với bất kỳ cái cây nào có bốn đỉnh, chỉ có hai loại hình dạng là 'ㄷ' và 'ㅈ'!

Đối với một cái cây bất kỳ có từ bốn đỉnh trở lên, hãy chọn một tập hợp gồm bốn đỉnh. Khi chỉ giữ lại các cạnh của cây gốc nối giữa hai đỉnh thuộc tập hợp này, nếu bốn đỉnh đó tạo thành một cấu trúc cây, thì nó sẽ có hình dạng 'ㄷ' hoặc 'ㅈ'. Gọi số lượng 'ㄷ' và 'ㅈ' trong cây lần lượt là số lượng các tập hợp gồm bốn đỉnh tạo thành hình dạng 'ㄷ' và 'ㅈ' trong cây đó.

Giờ đây, Dong-hyeon đã chia tất cả các cây trên thế giới thành ba loại như sau:

• D-cây: Cây có số lượng 'ㄷ' nhiều hơn 3 lần số lượng 'ㅈ'.
• G-cây: Cây có số lượng 'ㄷ' ít hơn 3 lần số lượng 'ㅈ'.
• DUDUDUNGA-cây: Cây có số lượng 'ㄷ' bằng đúng 3 lần số lượng 'ㅈ'.

Dong-hyeon vô cùng phấn khích và bắt đầu đếm số lượng 'ㄷ' và 'ㅈ' trong mọi cái cây mà cậu nhìn thấy. Tuy nhiên, ngay sau đó, một cái cây có tới 300.000 đỉnh xuất hiện trước mặt Dong-hyeon, khiến cậu hoàn toàn choáng váng. Hãy giúp Dong-hyeon xác định xem cái cây được cho là D-cây, G-cây hay DUDUDUNGA-cây!

Dữ liệu vào

Dòng đầu tiên chứa số đỉnh của cây $N$ ($4 \le N \le 300\,000$).

Từ dòng thứ hai trở đi, mỗi dòng trong số $N-1$ dòng tiếp theo chứa hai số $u, v$ là hai đỉnh được nối bởi một cạnh của cây ($1 \le u, v \le N$).

Dữ liệu ra

Nếu cái cây được cho là D-cây, hãy in ra D; nếu là G-cây, hãy in ra G; nếu là DUDUDUNGA-cây, hãy in ra DUDUDUNGA.

Ví dụ

Ví dụ 1

4
1 2
2 3
3 4

D

Ví dụ 2

4
1 2
1 3
1 4

G

Ví dụ 3

6
1 2
2 3
3 4
4 5
4 6

DUDUDUNGA

Hình dạng 'ㄷ' và 'ㅈ'