시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 7 6 6 85.714%

문제

Kocourkov라 불리는 체코 도시에는 화려한 공공 교통 시스템이 있다. 그것은 N개의 버스 정류장과 N - 1개의 양방향 도로로 이루어져있으며, 각각의 도로는 두개의 버스 정류장을 연결한다. 각각의 버스 정류장에서는 일련의 도로들을 이용하여 다른 모든 버스 정류장에 도달할 수 있다.

매일 아침, 모든 버스 정류장에서는 나머지 버스 정류장들로 정확히 한대의 버스가 출발한다. 즉, 전체적으로 N(N - 1)개의 버스들이 있다. 버스들은 경로에 있는 모든 버스정류장에 한번씩 정차한다.

모든 버스 정류장에서는 그곳에 정차하는 모든 버스들(그곳에서 그 경로를 시작하거나 경로를 끝내는 버스들을 포함한)을 나열한 시간표가 있어야한다.

당신은 Kocourkov의 교통 시스템에 대한 설명을 받았다. 도시의 모든 버스 정류장을 위해서 특정한 정류장에 정차하는 버스들의 수를 계산하라.

입력

첫번째 줄에는 도시의 버스 정류장의 수, 정수 N이 주어진다. 버스 정류장은 1번부터 N번까지 있다. 이후의 N - 1개의 줄은 도시의 도로를 나타낸다. 각각의 줄은 도로에 의해 연결된 두개의 다른 버스 정류장 번호 x, y( 1 ≤ x, y ≤ N)를 포함한다.

단 1 ≤ N ≤ 106이다.

출력

출력은 N개의 줄로 구성된다. i번째 줄에서는 i번 버스 정류장에 멈추는 버스의 수를 하나의 정수로 나타내야한다.

예제 입력

6
1 2
2 3
3 4
4 5
5 6

예제 출력

10
18
22
22
18
10

예제 입력 2

5
4 5
2 1
3 2
2 5

예제 출력 2

8
18
8
8
14

힌트