시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc1OCBcdWMyMTgsIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWQ2YzRcdWM3NTggTiAtIDFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOTA0XHVjNzQwIFx1YjNjNFx1Yjg1Y1x1YzVkMCBcdWM3NThcdWQ1NzQgXHVjNWYwXHVhY2IwXHViNDFjIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNSBcdWJjODhcdWQ2MzggeCwgeSgmbmJzcDsxICZsZTsgeCwgeSAmbGU7IE4pXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4IDEgJmxlOyBOICZsZTsgMTA8c3VwPjY8XC9zdXA+XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHVjMTFjXHViMjk0IGlcdWJjODggXHViYzg0XHVjMmE0IFx1YzgxNVx1Yjk1OFx1YzdhNVx1YzVkMCBcdWJhNDhcdWNkOTRcdWIyOTQgXHViYzg0XHVjMmE0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWQ1NThcdWIwOThcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjgxNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJ1cyBsaW5lcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIEN6ZWNoIGNpdHkgY2FsbGVkIEtvY291cmtvdiB0aGV5IGhhdmUgYSBzcGVjdGFjdWxhciBwdWJsaWMgdHJhbnNwb3J0YXRpb24gc3lzdGVtLiBJdCBjb25zaXN0cyBvZiBOIGJ1cyBzdG9wcyBhbmQgTiAmbWludXM7IDEgYmlkaXJlY3Rpb25hbCByb2FkcywgZWFjaCByb2FkIGNvbm5lY3RpbmcgdHdvIGJ1cyBzdG9wcy4gSXQgaXMgcG9zc2libGUgdG8gZ2V0IGZyb20gZWFjaCBidXMgc3RvcCB0byBldmVyeSBvdGhlciB1c2luZyBhIHNlcXVlbmNlIG9mIHJvYWRzLjxcL3A+XHJcblxyXG48cD5FdmVyeSBtb3JuaW5nLCBmb3IgZWFjaCBwYWlyIG9mIGRpc3RpbmN0IGJ1cyBzdG9wcyBhIGFuZCBiIHRoZXJlIGlzIGV4YWN0bHkgb25lIGJ1cyB0aGF0IHN0YXJ0cyBhdCAmbmJzcDthYW5kIGdvZXMgdG8gYiAoYWxvbmcgdGhlIG9ubHkgZGlyZWN0IHBhdGgpLiBUaGF0IGlzLCB0aGVyZSBhcmUgYSB0b3RhbCBvZiBOKE4gJm1pbnVzOyAxKSBidXNlcy4gRWFjaCBidXMgc3RvcHMgYXQgYWxsIGJ1cyBzdG9wcyBpdCB2aXNpdHMgYWxvbmcgdGhlIHdheS48XC9wPlxyXG5cclxuPHA+QXQgZXZlcnkgYnVzIHN0b3AgdGhlcmUgbXVzdCBiZSBhIHRpbWV0YWJsZSBsaXN0aW5nIGFsbCB0aGUgYnVzZXMgdGhhdCBzdG9wIHRoZXJlIChpbmNsdWRpbmcgYnVzZXMgdGhhdCBzdGFydCBvciBlbmQgdGhlaXIgam91cm5leSB0aGVyZSkuIFlvdSBhcmUgbm93IHdvbmRlcmluZyBob3cgbWFueSBidXNlcyBhcmUgbGlzdGVkIG9uIGVhY2ggdGltZXRhYmxlLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgdHJhZmZpYyBzeXN0ZW0gaW4gS29jb3Vya292LiBGb3IgZXZlcnkgYnVzIHN0b3AgaW4gdGhlIGNpdHkgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgYnVzZXMgdGhhdCBzdG9wIG9uIHRoYXQgcGFydGljdWxhciBzdG9wLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgYnVzIHN0b3BzIGluIHRoZSBjaXR5IChzdG9wcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4pLiBUaGUgZm9sbG93aW5nIE4gJm1pbnVzOyAxIGxpbmVzIGRlc2NyaWJlIHRoZSByb2FkcyBpbiB0aGUgY2l0eS4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgaW50ZWdlcnMgMSAmbGU7IHgsIHkgJmxlOyBOIG1lYW5pbmcgdGhhdCB0aGVyZSBpcyBhIHJvYWQgY29ubmVjdGluZyBidXMgc3RvcHMgeCBhbmQgeS48XC9wPlxyXG5cclxuPHA+SXQgaG9sZHMgMSAmbGU7IE4gJmxlOyAxMDxzdXA+NjxcL3N1cD48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnNpc3RzIG9mIE4gbGluZXMuIFRoZSBpLXRoIGxpbmUgc2hvdWxkIGNvbnRhaW4gYSBzaWdubGUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBidXNlcyB0aGF0IHN0b3Agb24gdGhlIGktdGggYnVzIHN0b3AuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d