시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 811 284 231 44.942%

문제

어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다!

정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자.

이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다.

  • D-트리 : ‘ㄷ’이 ‘ㅈ’의 $3$배보다 많은 트리
  • G-트리 : ‘ㄷ’이 ‘ㅈ’의 $3$배보다 적은 트리
  • DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 $3$배만큼 있는 트리

신이 난 동현이는 트리만 보이면 그 트리에 있는 ‘ㄷ’과 ‘ㅈ’이 몇 개인지 세고 다니기 시작했다. 하지만 곧 정점이 $30$만 개나 있는 트리가 동현이 앞에 나타났고, 동현이는 그만 정신을 잃고 말았다. 동현이를 대신해 주어진 트리가 D-트리인지 G-트리인지 아니면 DUDUDUNGA-트리인지 알려주자!

입력

첫 번째 줄에 트리의 정점 수 $N$이 주어진다. ($4 \leq N \leq 300\ 000$)

두 번째 줄부터 $N-1$개의 줄에 트리의 각 간선이 잇는 두 정점의 번호 $u$, $v$가 주어진다. ($1 \leq u, v \leq 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