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

문제

$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 당신은 $T$의 각 정점 $i (1 \leq i \leq N)$에 $1$이상 $N$이하의 서로 다른 수 $P(i)$를 배정하려고 한다. 즉, $P$가 순열이 되게 수를 배정한다.

어떤 정점 $v$에 대해, 인접한 정점들을 $\left\{ u_1, \, u_2, \, \cdots, \, u_k \right\}$라 하자. 이때, 정점 $v$에 배정된 값 $P(v)$가 집합 $\{P(v), P(u_1), P(u_2), \cdots, P(u_k) \}$의 중앙값이라면 ($P(v)$ 가 포함됨에 유의하라), 정점 $v$를 보통의 정점이라 한다. 모든 정점이 보통의 정점이 되도록 순열 $P$를 구성하자.

원소가 $k$개 있는 집합을 오름차순으로 정렬했을 때,

  • $k$가 홀수라면 가운데에 위치한 하나의 값을 중앙값이라 한다.
  • $k$가 짝수라면 가운데에 위치한 두 개의 값 모두를 중앙값으로 인정한다.

입력

첫 번째 줄에 $N$이 주어진다. ($2 \leq N \leq 100 \,000$)

두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선 $u, v$가 공백으로 구분되어 주어진다. ($1 \leq u, v \leq N$)

출력

첫 번째 줄에 $N$개의 수를 공백으로 구분하여 출력하라. $i (1 \leq i \leq N)$번째 수는 정점 $i$에 적힌 수 $P(i)$이다. $P$는 순열이어야 한다.

예제 입력 1

5
1 2
2 3
2 5
1 4

예제 출력 1

2 4 5 1 3

위 예제는 아래 그림과 같다.