나무 위에 도토리를 저장하는 $N$마리의 다람쥐가 있습니다. 트리는 $1$부터 $N$까지 번호가 매겨진 $N$개의 정점과 $N-1$개의 무방향 간선으로 이루어진 연결 그래프입니다. 각 다람쥐는 트리의 서로 다른 정점에 앉아 있으며, 두 다람쥐는 그들의 정점이 간선으로 연결되어 있으면 이웃입니다.

정점 번호가 작은 순서대로, 즉 정점 $1$에 있는 다람쥐부터 시작하여 각 다람쥐는 현재 도토리를 가장 많이 가지고 있는 이웃 다람쥐로부터 도토리 한 개를 훔칩니다. 만약 도토리를 가장 많이 가진 이웃이 여러 마리라면, 그 다람쥐는 그들 각각으로부터 도토리를 한 개씩 훔칩니다!

이러한 소동의 여파를 제한하기 위해, 각 다람쥐가 처음에 최소 $N$개의 도토리를 가지도록(도난으로 인해 도토리가 바닥나지 않도록) 분배하고, $N$마리의 다람쥐가 서로 도둑질을 모두 마친 후에도 처음에 가졌던 도토리 개수와 동일한 개수를 가지도록 도토리를 분배하고자 합니다. 모든 다람쥐가 처음에 최대 $2N-1$개의 도토리를 가지는 그러한 분배가 존재함이 알려져 있습니다. 이러한 조건을 만족하는 임의의 분배를 찾으십시오.

입력

첫 번째 줄에는 정점(및 다람쥐)의 수인 정수 $N$ ($2 \le N \le 10^5$)이 주어집니다.

이어지는 $N-1$개의 줄에는 각각 두 개의 정수 $u$와 $v$ ($1 \le u, v \le N, u \neq v$)가 주어지며, 이는 정점 $u$와 $v$ 사이에 간선이 존재함을 나타냅니다. 임의의 두 정점 사이에는 최대 하나의 간선이 존재하며, 간선들은 트리를 형성합니다.

출력

정점 $i$에 있는 다람쥐에게 분배할 도토리의 개수를 $d_i$라고 할 때, $N \le d_i \le 2N-1$을 만족하는 $N$개의 정수 $d_1, d_2, \dots, d_N$을 공백으로 구분하여 출력하십시오. 모든 다람쥐가 도둑질을 마친 후 처음에 시작했던 도토리 개수와 동일한 개수를 가지게 된다면 정답으로 인정됩니다. 이러한 도토리 분배는 항상 존재함이 증명되어 있습니다.

예제

예제 입력 1

5
1 2
1 3
1 4
2 5

예제 출력 1

6 5 7 7 9

예제 입력 2

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

예제 출력 2

14 15 10 9 13 14 14 14