시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 24 14 13 68.421%

문제

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번 버스 정류장에 멈추는 버스의 수를 하나의 정수로 나타내야한다.

예제 입력 1

6
1 2
2 3
3 4
4 5
5 6

예제 출력 1

10
18
22
22
18
10

예제 입력 2

5
4 5
2 1
3 2
2 5

예제 출력 2

8
18
8
8
14
W3sicHJvYmxlbV9pZCI6IjEyODE3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzg0XHVjMmE0IFx1YjE3OFx1YzEyMCIsImRlc2NyaXB0aW9uIjoiPHA+S29jb3Vya292XHViNzdjIFx1YmQ4OFx1YjlhY1x1YjI5NCBcdWNjYjRcdWNmNTQgXHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1ZDY1NFx1YjgyNFx1ZDU1YyBcdWFjZjVcdWFjZjUgXHVhZDUwXHVkMWI1IFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YWM4M1x1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWFjZmMgTiAtIDFcdWFjMWNcdWM3NTggXHVjNTkxXHViYzI5XHVkNWE1IFx1YjNjNFx1Yjg1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMFx1YzExY1x1YjI5NCBcdWM3N2NcdWI4MjhcdWM3NTggXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWIyZTRcdWI5NzggXHViYWE4XHViNGUwIFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjgsIFx1YmFhOFx1YjRlMCBcdWJjODRcdWMyYTQgXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjXHViMjk0IFx1YjA5OFx1YmEzOFx1YzljMCBcdWJjODRcdWMyYTQgXHVjODE1XHViOTU4XHVjN2E1XHViNGU0XHViODVjIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWNcdWIzMDBcdWM3NTggXHViYzg0XHVjMmE0XHVhYzAwIFx1Y2Q5Y1x1YmMxY1x1ZDU1Y1x1YjJlNC4mbmJzcDtcdWM5ODksIFx1YzgwNFx1Y2NiNFx1YzgwMVx1YzczY1x1Yjg1YyBOKE4gLSAxKVx1YWMxY1x1Yzc1OCBcdWJjODRcdWMyYTRcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWJjODRcdWMyYTRcdWI0ZTRcdWM3NDAgXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYzg0XHVjMmE0XHVjODE1XHViOTU4XHVjN2E1XHVjNWQwIFx1ZDU1Y1x1YmM4OFx1YzUyOSBcdWM4MTVcdWNjMjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWJjODRcdWMyYTQgXHVjODE1XHViOTU4XHVjN2E1XHVjNWQwXHVjMTFjXHViMjk0IFx1YWRmOFx1YWNmM1x1YzVkMCBcdWM4MTVcdWNjMjhcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YmM4NFx1YzJhNFx1YjRlNChcdWFkZjhcdWFjZjNcdWM1ZDBcdWMxMWMgXHVhZGY4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjNzBcdWIwOTggXHVhY2JkXHViODVjXHViOTdjIFx1YjA1ZFx1YjBiNFx1YjI5NCBcdWJjODRcdWMyYTRcdWI0ZTRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTVjKVx1Yzc0NCBcdWIwOThcdWM1ZjRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVkNDVjXHVhYzAwIFx1Yzc4OFx1YzViNFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIEtvY291cmtvdlx1Yzc1OCBcdWFkNTBcdWQxYjUgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWMxMjRcdWJhODVcdWM3NDQgXHViYzFiXHVjNTU4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWM3NTggXHViYWE4XHViNGUwIFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDQgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDAgXHVjODE1XHVjYzI4XHVkNTU4XHViMjk0IFx1YmM4NFx1YzJhNFx1YjRlNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NTggXHVjMjE4LCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVkNmM0XHVjNzU4IE4gLSAxXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0MCBcdWIzYzRcdWMyZGNcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzkwNFx1Yzc0MCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWI0NTBcdWFjMWNcdWM3NTggXHViMmU0XHViOTc4IFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTUgXHViYzg4XHVkNjM4IHgsIHkoJm5ic3A7MSAmbGU7IHgsIHkgJmxlOyBOKVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOCAxICZsZTsgTiAmbGU7IDEwPHN1cD42PFwvc3VwPlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YzExY1x1YjI5NCBpXHViYzg4IFx1YmM4NFx1YzJhNCBcdWM4MTVcdWI5NThcdWM3YTVcdWM1ZDAgXHViYTQ4XHVjZDk0XHViMjk0IFx1YmM4NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTI4MTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdXMgbGluZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBDemVjaCBjaXR5IGNhbGxlZCBLb2NvdXJrb3YgdGhleSBoYXZlIGEgc3BlY3RhY3VsYXIgcHVibGljIHRyYW5zcG9ydGF0aW9uIHN5c3RlbS4gSXQgY29uc2lzdHMgb2YgTiBidXMgc3RvcHMgYW5kIE4gJm1pbnVzOyAxIGJpZGlyZWN0aW9uYWwgcm9hZHMsIGVhY2ggcm9hZCBjb25uZWN0aW5nIHR3byBidXMgc3RvcHMuIEl0IGlzIHBvc3NpYmxlIHRvIGdldCBmcm9tIGVhY2ggYnVzIHN0b3AgdG8gZXZlcnkgb3RoZXIgdXNpbmcgYSBzZXF1ZW5jZSBvZiByb2Fkcy48XC9wPlxyXG5cclxuPHA+RXZlcnkgbW9ybmluZywgZm9yIGVhY2ggcGFpciBvZiBkaXN0aW5jdCBidXMgc3RvcHMgYSBhbmQgYiB0aGVyZSBpcyBleGFjdGx5IG9uZSBidXMgdGhhdCBzdGFydHMgYXQgJm5ic3A7YWFuZCBnb2VzIHRvIGIgKGFsb25nIHRoZSBvbmx5IGRpcmVjdCBwYXRoKS4gVGhhdCBpcywgdGhlcmUgYXJlIGEgdG90YWwgb2YgTihOICZtaW51czsgMSkgYnVzZXMuIEVhY2ggYnVzIHN0b3BzIGF0IGFsbCBidXMgc3RvcHMgaXQgdmlzaXRzIGFsb25nIHRoZSB3YXkuPFwvcD5cclxuXHJcbjxwPkF0IGV2ZXJ5IGJ1cyBzdG9wIHRoZXJlIG11c3QgYmUgYSB0aW1ldGFibGUgbGlzdGluZyBhbGwgdGhlIGJ1c2VzIHRoYXQgc3RvcCB0aGVyZSAoaW5jbHVkaW5nIGJ1c2VzIHRoYXQgc3RhcnQgb3IgZW5kIHRoZWlyIGpvdXJuZXkgdGhlcmUpLiBZb3UgYXJlIG5vdyB3b25kZXJpbmcgaG93IG1hbnkgYnVzZXMgYXJlIGxpc3RlZCBvbiBlYWNoIHRpbWV0YWJsZS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIHRyYWZmaWMgc3lzdGVtIGluIEtvY291cmtvdi4gRm9yIGV2ZXJ5IGJ1cyBzdG9wIGluIHRoZSBjaXR5IGNhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIGJ1c2VzIHRoYXQgc3RvcCBvbiB0aGF0IHBhcnRpY3VsYXIgc3RvcC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIGJ1cyBzdG9wcyBpbiB0aGUgY2l0eSAoc3RvcHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOKS4gVGhlIGZvbGxvd2luZyBOICZtaW51czsgMSBsaW5lcyBkZXNjcmliZSB0aGUgcm9hZHMgaW4gdGhlIGNpdHkuIEVhY2ggbGluZSBjb250YWlucyB0d28gZGlmZmVyZW50IGludGVnZXJzIDEgJmxlOyB4LCB5ICZsZTsgTiBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSByb2FkIGNvbm5lY3RpbmcgYnVzIHN0b3BzIHggYW5kIHkuPFwvcD5cclxuXHJcbjxwPkl0IGhvbGRzIDEgJmxlOyBOICZsZTsgMTA8c3VwPjY8XC9zdXA+PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBjb25zaXN0cyBvZiBOIGxpbmVzLiBUaGUgaS10aCBsaW5lIHNob3VsZCBjb250YWluIGEgc2lnbmxlIGludGVnZXIsIHRoZSBudW1iZXIgb2YgYnVzZXMgdGhhdCBzdG9wIG9uIHRoZSBpLXRoIGJ1cyBzdG9wLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==