시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 90 19 13 18.571%

문제

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+XHJcblxyXG48cD5cdWJjMjlcdWJiMzhcdWQ1NWMgXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAxXHVjNzNjXHViYTc0IFx1YWUzOFx1Yzc3NCBuXHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzBhY1x1YWNmY1x1YWMwMCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YWNmY1x1YjA5OFx1YmIzNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAyNTAwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBuJm1pbnVzOzEgXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzA0XHVjMTIwXHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggcywgZVx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWJhNzAsIHNcdWJjODggXHVjODE1XHVjODEwXHVhY2ZjIGVcdWJjODggXHVjODE1XHVjODEwXHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YjI5NCBcdWJhYThcdWI0NTAgMVx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBzLCBlICZsZTsgbiwgcyAmbmU7IGUpLjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWM1ZjBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBhY1x1YWNmY1x1YjA5OFx1YmIzNFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQgKFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzVjNlx1YjJlNCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGFjXHVhY2ZjXHVhYzAwIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC82NDMyMDljNy1hMGIyLTQ1MjktODk2OS1lZjAzYzk1YjUyOWNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDE5MnB4OyBoZWlnaHQ6IDEzMHB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwMTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKb3VybmV5IiwiZGVzY3JpcHRpb24iOiI8cD5CeXRlYXNhciBpcyBhIGdsb2JldHJvdHRlci4gSGUgaXMgcGxhbm5pbmcgYSBuZXcgam91cm5leSB0aGF0IGhlIHdvdWxkIGxpa2UgdG8gYmUgdGhlIGxvbmdlc3Qgam91cm5leSBpbiBoaXMgbGlmZS4gSGUgaGFzIGFscmVhZHkgc2VsZWN0ZWQgQnl0ZWxhbmQsIGFuIGlzbGFuZCBjb3VudHJ5LCBhcyB0aGUgZGVzdGluYXRpb24gb2YgdGhlIGpvdXJuZXkuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSA8ZW0+bjxcL2VtPiB0b3ducyBpbiBCeXRlbGFuZCwgbnVtYmVyZWQgMSB0aHJvdWdoIG4uIFRoZSByb2FkIG5ldHdvcmsgaW4gQnl0ZWxhbmQgYWxsb3dzIHRvIHRyYXZlbCBiZXR3ZWVuIGV2ZXJ5IHBhaXIgb2YgdG93bnMgaW4gZXhhY3RseSBvbmUgd2F5LiBFdmVyeSByb2FkIGhhcyB0aGUgc2FtZSBsZW5ndGguPFwvcD5cclxuXHJcbjxwPkJ5dGVhc2FyIGRlY2lkZWQgdG8gdmlzaXQgYWxsIHRoZSB0b3ducyBpbiBCeXRlbGFuZCBvbiBoaXMgam91cm5leS4gVGhlIGpvdXJuZXkgd2lsbCBzdGFydCBhdCB0aGUgdG93biBuby4gMSBhbmQgY29udGludWUgZWFjaCB0aW1lIHRvIHRoZSBmdXJ0aGVzdCBub24tdmlzaXRlZCB0b3duICh0aGUgdG93bnMgdGhhdCBhcmUgbG9jYXRlZCBvbiB0aGUgd2F5IHRvIHRoYXQgdG93biBkbyBub3QgY291bnQgYXMgdmlzaXRlZCkuIElmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgdG93biB0aGF0IGNvdWxkIGJlIHNlbGVjdGVkLCBCeXRlYXNhciBjaG9vc2VzIHRoZSBvbmUgd2l0aCB0aGUgYmlnZ2VzdCBudW1iZXIuPFwvcD5cclxuXHJcbjxwPkJ5dGVhc2FyIGlzIHJlYWxseSBleGNpdGVkIGFib3V0IGhpcyBqb3VybmV5IHBsYW4uIEhlbHAgaGltIGZpbmQgdGhlIGxpc3Qgb2YgdG93bnMgaW4gdGhlIG9yZGVyIHRoZXkgd2lsbCBiZSB2aXNpdGVkIGFsb25nIHRoZSB3YXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciA8ZW0+bjxcL2VtPiAoMSAmbGU7IDxlbT5uPFwvZW0+ICZsZTsgMjUwIDAwMCksIHRoZSBudW1iZXIgb2YgdG93bnMgaW4gQnl0ZWxhbmQuIFRoZSBmb2xsb3dpbmcgPGVtPm48XC9lbT4gJm1pbnVzOyAxIGxpbmVzIGRlc2NyaWJlIHRoZSByb2Fkcy4gRWFjaCBvZiB0aG9zZSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgPGVtPmE8c3ViPmk8XC9zdWI+PFwvZW0+LCA8ZW0+YjxzdWI+aTxcL3N1Yj48XC9lbT4gKDEgJmxlOyA8ZW0+YTxzdWI+aTxcL3N1Yj48XC9lbT4sIDxlbT5iPHN1Yj5pPFwvc3ViPjxcL2VtPiAmbGU7IDxlbT5uPFwvZW0+LCA8ZW0+YTxzdWI+aTxcL3N1Yj48XC9lbT4mbmJzcDsmbmU7IDxlbT5iPHN1Yj5pPFwvc3ViPjxcL2VtPikgdGhhdCByZXByZXNlbnQgYSBiaWRpcmVjdGlvbmFsIHJvYWQgY29ubmVjdGluZyB0b3ducyA8ZW0+YTxzdWI+aTxcL3N1Yj48XC9lbT4gYW5kIDxlbT5iPHN1Yj5pPFwvc3ViPjxcL2VtPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHBlcm11dGF0aW9uIG9mIG51bWJlcnMgezEsIC4gLiAuICwgPGVtPm48XC9lbT59IHRoYXQgc2hvd3MgdGhlIG9yZGVyIG9mIHZpc2l0aW5nIHRvd25zIGluIEJ5dGVsYW5kLjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzY0MzIwOWM3LWEwYjItNDUyOS04OTY5LWVmMDNjOTViNTI5Y1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTkycHg7IGhlaWdodDogMTMwcHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=