Problem
Asya는 동물을 아주 좋아합니다. 그녀는 최근 n마리의 새끼 고양이를 구입하고 1에서 n까지의 숫자 식별자를 부여하고 인클로저에 넣었습니다. 조류 사육장은 n개의 셀로 이루어진 행이며 역시 1부터 n까지 번호가 매겨져 있습니다. 인접한 셀은 메쉬 파티션으로 구분되며 인클로저에는 총 n & 마이너스 1개의 파티션이 있습니다. 처음에는 각 셀에 숫자가 있는 정확히 한 마리의 새끼 고양이가 정착했습니다.
새끼 고양이를 보면서 Asya는 그들이 매우 친절하고 이웃 셀에 사는 새끼 고양이 몇 쌍이 서로 놀고 싶어한다는 것을 알았습니다. 이 즐거움을 빼앗지 않기 위해 Asya는 인접한 셀 사이의 칸막이를 제거하여 더 크게 만들기 시작했습니다.
i일째에 Asya는 다음을 수행했습니다.
i번째 날에 이웃 셀에 살고 있는 새끼 고양이 x
i와 y
i가 놀고 싶어한다는 것을 알아차렸습니다.
나는 이 셀 사이의 칸막이를 제거하여 하나로 만들었습니다. 이전 두 셀의 모든 새끼 고양이가 끝났습니다.
Asya는 파티션을 반환하지 않았기 때문에 n & 마이너스; 1 일 후에 인클로저는 모든 새끼 고양이가 사는 단일 셀이되었습니다. 매우 현명하게 Asya는 특별한 일지에 n−1일마다 새끼 고양이 ID x
i 및 y
i를 적었습니다.
당신은 이 정보가 담긴 잡지를 받았지만 처음에 새끼 고양이가 감방에 어떻게 정착했는지 알지 못합니다. 로그의 데이터와 모순되지 않는 n개의 원래 셀에서 새끼 고양이의 분포를 찾으십시오.
입력
첫 번째 줄에는 정수 n이 포함됩니다(
\(2 \leq n \leq 150000\)) — 새끼 고양이의 수.
다음 n−1 행에는 정수 쌍 x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — i일에 파티션이 제거된 세포 사이의 새끼 고양이 식별자. 이전 셀 병합의 결과로 새끼 고양이 xi와 yi가 동일한 셀에 있지 않음이 보장됩니다.
출판물
n개의 고유한 정수 p
i(
\(1 \leq p_i \leq n\))를 출력합니다. 여기서 p
i — 원래 셀 번호 i에 살았던 새끼 고양이의 식별자. 가능한 답변이 여러 개인 경우 그 중 하나를 인쇄하십시오.
참고
예를 들어, 답변에서 새끼 고양이의 가능한 초기 정착지 중 하나가 제공되고 다른 답변이 있습니다. 아래 이미지는 새끼 고양이의 초기 배치를 위해 세포가 어떻게 병합되었는지 보여줍니다. 이 배치로 인해 Asya의 저널에 따라 매일 친구가 된 새끼 고양이는 인접한 셀에 있습니다.
<몸>
| 입력 |
출력 |
5
14
25
3 1
4 5 |
3 1 4 2 5 |