시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 60 10 7 13.208%

문제

n개의 정점으로 이루어진 가중치 없는 사과나무가 있고, 1번 정점에 사과 한 알이 매달려 있다.

여행을 좋아하는 사과는 사과나무의 모든 정점을 정확히 방문하려고 한다. 사과는 방문하지 않은 정점 중 현재 사과의 위치와 가장 거리가 큰 정점으로 움직이며, 그러한 정점이 여러 개일 경우 가장 번호가 큰 정점을 방문한다.

방문한 정점의 번호를 순서대로 적으면 길이 n의 순열을 얻을 수 있을 것이다. 사과가 n개의 정점을 방문한 순서를 출력하여라.

입력

첫번째 줄에 사과나무의 정점의 수 n이 주어진다. (1 ≤ n ≤ 250000)

이후 n−1 개의 줄에 걸쳐 간선이 주어진다. 간선은 두 정수 s, e로 표현되며, s번 정점과 e번 정점을 잇는 간선이 존재함을 뜻한다. 간선의 가중치는 모두 1이다. (1 ≤ s, e ≤ n, s ≠ e).

당연하지만, 사과나무는 트리이다 (연결되어 있고 사이클이 없다).

출력

사과가 방문한 정점의 순서를 출력하라.

예제 입력 1

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

예제 출력 1

1 7 4 6 3 5 2

힌트

W3sicHJvYmxlbV9pZCI6IjEwMDE0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVHJhdmVsaW5nIFNhZ2EgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+blx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWMwMFx1YzkxMVx1Y2U1OCBcdWM1YzZcdWIyOTQgXHVjMGFjXHVhY2ZjXHViMDk4XHViYjM0XHVhYzAwIFx1Yzc4OFx1YWNlMCwgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjMGFjXHVhY2ZjIFx1ZDU1YyBcdWM1NGNcdWM3NzQgXHViOWU0XHViMmVjXHViODI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVkNTg5XHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWFjZmNcdWIyOTQgXHVjMGFjXHVhY2ZjXHViMDk4XHViYjM0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjODE1XHVkNjU1XHVkNzg4IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBhY1x1YWNmY1x1YjI5NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzgxNVx1YzgxMCBcdWM5MTEgXHVkNjA0XHVjN2FjIFx1YzBhY1x1YWNmY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVhYzAwXHVjN2E1IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWQwNzAgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3MCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzdjIFx1YWNiZFx1YzZiMCBcdWFjMDBcdWM3YTUgXHViYzg4XHVkNjM4XHVhYzAwIFx1ZDA3MCBcdWM4MTVcdWM4MTBcdWM3NDQgXHViYzI5XHViYjM4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWJiMzhcdWQ1NWMgXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNzNjXHViYTc0IFx1YWUzOFx1Yzc3NCBuXHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzBhY1x1YWNmY1x1YWMwMCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGFjXHVhY2ZjXHViMDk4XHViYjM0XHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDI1MDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IG4mbWludXM7MSBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDRcdWMxMjBcdWM3NDAgXHViNDUwIFx1YzgxNVx1YzIxOCBzLCBlXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YmE3MCwgc1x1YmM4OCBcdWM4MTVcdWM4MTBcdWFjZmMgZVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NjhcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LiBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHViMjk0IFx1YmFhOFx1YjQ1MCAxXHVjNzc0XHViMmU0LiAoMSAmbGU7IHMsIGUgJmxlOyBuLCBzICZuZTsgZSkuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzVmMFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMGFjXHVhY2ZjXHViMDk4XHViYjM0XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNCAoXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNWM2XHViMmU0KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYWNcdWFjZmNcdWFjMDAgXHViYzI5XHViYjM4XHVkNTVjIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzY0MzIwOWM3LWEwYjItNDUyOS04OTY5LWVmMDNjOTViNTI5Y1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTkycHg7IGhlaWdodDogMTMwcHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDAxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkpvdXJuZXkiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVhc2FyIGlzIGEgZ2xvYmV0cm90dGVyLiBIZSBpcyBwbGFubmluZyBhIG5ldyBqb3VybmV5IHRoYXQgaGUgd291bGQgbGlrZSB0byBiZSB0aGUgbG9uZ2VzdCBqb3VybmV5IGluIGhpcyBsaWZlLiBIZSBoYXMgYWxyZWFkeSBzZWxlY3RlZCBCeXRlbGFuZCwgYW4gaXNsYW5kIGNvdW50cnksIGFzIHRoZSBkZXN0aW5hdGlvbiBvZiB0aGUgam91cm5leS48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIDxlbT5uPFwvZW0+IHRvd25zIGluIEJ5dGVsYW5kLCBudW1iZXJlZCAxIHRocm91Z2ggbi4gVGhlIHJvYWQgbmV0d29yayBpbiBCeXRlbGFuZCBhbGxvd3MgdG8gdHJhdmVsIGJldHdlZW4gZXZlcnkgcGFpciBvZiB0b3ducyBpbiBleGFjdGx5IG9uZSB3YXkuIEV2ZXJ5IHJvYWQgaGFzIHRoZSBzYW1lIGxlbmd0aC48XC9wPlxyXG5cclxuPHA+Qnl0ZWFzYXIgZGVjaWRlZCB0byB2aXNpdCBhbGwgdGhlIHRvd25zIGluIEJ5dGVsYW5kIG9uIGhpcyBqb3VybmV5LiBUaGUgam91cm5leSB3aWxsIHN0YXJ0IGF0IHRoZSB0b3duIG5vLiAxIGFuZCBjb250aW51ZSBlYWNoIHRpbWUgdG8gdGhlIGZ1cnRoZXN0IG5vbi12aXNpdGVkIHRvd24gKHRoZSB0b3ducyB0aGF0IGFyZSBsb2NhdGVkIG9uIHRoZSB3YXkgdG8gdGhhdCB0b3duIGRvIG5vdCBjb3VudCBhcyB2aXNpdGVkKS4gSWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSB0b3duIHRoYXQgY291bGQgYmUgc2VsZWN0ZWQsIEJ5dGVhc2FyIGNob29zZXMgdGhlIG9uZSB3aXRoIHRoZSBiaWdnZXN0IG51bWJlci48XC9wPlxyXG5cclxuPHA+Qnl0ZWFzYXIgaXMgcmVhbGx5IGV4Y2l0ZWQgYWJvdXQgaGlzIGpvdXJuZXkgcGxhbi4gSGVscCBoaW0gZmluZCB0aGUgbGlzdCBvZiB0b3ducyBpbiB0aGUgb3JkZXIgdGhleSB3aWxsIGJlIHZpc2l0ZWQgYWxvbmcgdGhlIHdheS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIDxlbT5uPFwvZW0+ICgxICZsZTsgPGVtPm48XC9lbT4gJmxlOyAyNTAgMDAwKSwgdGhlIG51bWJlciBvZiB0b3ducyBpbiBCeXRlbGFuZC4gVGhlIGZvbGxvd2luZyA8ZW0+bjxcL2VtPiAmbWludXM7IDEgbGluZXMgZGVzY3JpYmUgdGhlIHJvYWRzLiBFYWNoIG9mIHRob3NlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyA8ZW0+YTxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5iPHN1Yj5pPFwvc3ViPjxcL2VtPiAoMSAmbGU7IDxlbT5hPHN1Yj5pPFwvc3ViPjxcL2VtPiwgPGVtPmI8c3ViPmk8XC9zdWI+PFwvZW0+ICZsZTsgPGVtPm48XC9lbT4sIDxlbT5hPHN1Yj5pPFwvc3ViPjxcL2VtPiZuYnNwOyZuZTsgPGVtPmI8c3ViPmk8XC9zdWI+PFwvZW0+KSB0aGF0IHJlcHJlc2VudCBhIGJpZGlyZWN0aW9uYWwgcm9hZCBjb25uZWN0aW5nIHRvd25zIDxlbT5hPHN1Yj5pPFwvc3ViPjxcL2VtPiBhbmQgPGVtPmI8c3ViPmk8XC9zdWI+PFwvZW0+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgcGVybXV0YXRpb24gb2YgbnVtYmVycyB7MSwgLiAuIC4gLCA8ZW0+bjxcL2VtPn0gdGhhdCBzaG93cyB0aGUgb3JkZXIgb2YgdmlzaXRpbmcgdG93bnMgaW4gQnl0ZWxhbmQuPFwvcD5cclxuIiwiaGludCI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNjQzMjA5YzctYTBiMi00NTI5LTg5NjktZWYwM2M5NWI1MjljXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAxOTJweDsgaGVpZ2h0OiAxMzBweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==