35033번 - 용사 스페셜 저지

문제

한때 용사파티의 마법사였던 프리렌이 봉인하였던 마왕 “크크발”이 800년의 시간이 지나 부활에 임박하였다! 이에 프리렌은 “크크발”을 확실하게 해치우고자 한다. 크크발은 무덤에 있는 비석들에 쪼개져 잠들어 있다. 지금 당장 무덤 일대를 날려버리면 좋겠지만, 크크발의 조각이 풀려나면서 주변에 새기는 저주의 낙인은 정말 강력하기 때문에 프리렌은 신중하게 비석(과 그 안에 잠들어있는 크크발의 조각)을 하나하나 제거하기로 하였다.

프리렌은 마왕 크크발을 $N$개의 비석에 나누어서 봉인했다. 또 비석 사이에는 두 비석을 양쪽으로 잇는 $N-1$개의 길이 있다. 어떤 비석에서 시작해도 길을 통해 다른 모든 비석에 도달할 수 있다. 즉, 비석과 길은 트리 구조를 이룬다.

프리렌은 다음과 같은 정화 의식을 여러 번 수행하여 모든 비석을 제거하고자 한다. 정화 의식을 수행하면 다음과 같은 일이 차례대로 일어난다.

1. 현재 직접 연결된 비석의 개수가 하나 이하인 비석을 고른 후 제거한다. 그 비석에 저주의 낙인이 있었다면, 낙인도 같이 사라진다.
2. 해당 비석과 직접 연결되었던 비석에 저주의 낙인이 새겨진다. 이미 저주의 낙인이 있었다면 아무런 변화도 일어나지 않는다.

만약 프리렌이 비석을 제거하던 도중, 어떠한 시점에라도 저주의 낙인이 새겨진 비석의 개수가 20ドル$개를 넘어가는 시점이 온다면, 크크발은 곧장 부활하여 세계에 막대한 위협을 줄 것이다. 또한, 1ドル$번 비석에는 크크발의 영혼이 봉인되어 있기 때문에, 1ドル$번 비석을 제거하기 전에 다른 모든 비석이 제거되어 있어야 한다.

프리렌은 당신에게 마법의 재능이 있는지 확인하기 위해서, 어느 순서로 비석을 제거해야 하는지를 물어보았다. 위의 조건을 만족하도록 비석을 전부 제거하는 순서를 출력하라.

입력

첫 번째 줄에 양의 정수 $N$이 주어진다.

이후 $N-1$개의 줄에 걸쳐 두 정수 $u,v$가 공백으로 구분되어 주어진다. 이는 $u$번 비석과 $v$번 비석 사이에 길이 있음을 의미한다.

출력

첫 번째 줄에 $N$개의 수를 공백으로 구분하여 출력한다. 이중 $i$번째 수는 프리렌이 해당 번호의 비석을 $i$번째로 제거함을 의미한다. 1ドル$번 비석은 마지막에 제거되어야 하며, 어떠한 시점이라도 저주의 낙인이 새겨진 비석의 개수가 20ドル$개를 넘어서는 안 된다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル\le N\le 200,円 000$
• 1ドル\le u,v\le N$
• $N$개의 비석과 $N-1$개의 길은 트리 구조를 이룬다.

노트