시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB26614112352.119%

문제

동우와 혁준이는 동까뚱뽭 게임을 하려 한다. 동까뚱뽭 게임은 정점의 개수가 $N$개이고, $1$번 정점을 루트로 하는 트리 위의 정점에 존재하는 한 개의 말을 옮기며 진행하는 게임이다. 게임을 시작하는 정점을 $1$번부터 $N$번까지 하여 총 $N$번의 게임을 진행하며 각 게임은 시작 정점에 말을 두고 난 뒤 시작한다. 진행 방식은 다음과 같다.

  1. 현재 말이 있는 정점이 말단 정점(leaf node)라면 4번으로 이동한다.
  2. 현재 턴의 플레이어는 현재 말이 있는 정점의 자식 정점들 중 하나로 옮기고 1점을 얻는다.
  3. 턴을 상대방에게 넘긴 후 1번으로 돌아간다.
  4. 점수가 높은 사람이 승리하고 게임을 종료한다.

동우는 게임의 제왕 혁준이에게 상대가 안 되기 때문에 선공을 가져간다. 대신 동점일 경우에는 혁준이가 이긴다.

두 사람 모두 최적의 방법으로 게임을 했다고 가정하자.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 100\,000)$

두 번째 줄부터 $N-1$개의 줄에 간선 정보 $u,v$가 공백으로 구분되어 주어진다. 이는 두 정점 $u,v$가 간선으로 연결되어 있음을 의미한다. $u,v$는 정수이고 같은 간선 정보는 주어지지 않는다. $(1 \le u,v \le N; u \neq v)$

입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.

출력

$i$번 정점에서 게임을 시작했을 때 동우가 이긴다면 donggggas를 혁준이가 이긴다면 uppercut을 $i$번째 줄에 출력한다. $(1 \le i \le N)$

예제 입력 1

9
1 4
1 5
2 4
1 3
5 6
6 7
6 8
8 9

예제 출력 1

donggggas
uppercut
uppercut
donggggas
uppercut
donggggas
uppercut
donggggas
uppercut