32645번 - 동까뚱뽭 게임

문제

동우와 혁준이는 동까뚱뽭 게임을 하려 한다. 동까뚱뽭 게임은 정점의 개수가 $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)$

제한

힌트