균형
시간 제한1초메모리 제한512 MB
트리가 주어질 때, 각 정점에서 뒤에 오는 이웃 수와 앞에 오는 이웃 수의 차의 절댓값 합이 최소가 되도록 정점 순서를 정한다.
문제
트리토피아에서 시장 선거가 열린다! 알다시피 트리토피아는 상당히 독특한 나라로, 모든 도시 쌍 사이를 이동하는 방법이 정확히 하나씩 존재한다. 두 도시 사이를 이동할 때 중간에 다른 도시를 거치지 않고 갈 수 있으면 그 두 도시는 이웃이라고 하며, 이웃 도시 사이의 관계는 무척 특별하다.
지금 개표가 진행 중이고, 머지않아 공영 방송에서 결과가 발표될 예정이다. 올해는 트리토피아의 n개 도시마다 선거 참관인이 한 명씩 배치되어 문제를 발견하면 보고한다. 모든 참관인은 결과가 발표되는 순서에 매우 까다롭다. 특히 도시 i의 참관인은 i번째 도시의 이웃 중 i번째 도시보다 먼저 발표된 도시의 수(bi)와 i번째 도시보다 나중에 발표된 이웃 도시의 수(ai)를 센다.
참관인은 ai가 bi와 같기를 기대한다. 실제로 두 수가 다른 만큼, 즉 |ai − bi|만큼 참관인은 불만 편지를 보낸다. 쓸모없는 편지가 산더미처럼 쌓이는 것을 피하고 싶은 당신은, 받는 불만의 총 개수를 최소화하려면 어떤 순서를 골라야 하는지 고민한다.
입력
첫째 줄에 트리토피아의 도시 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100 000)이 주어진다. 이어서 n − 1개 줄이 주어지고, i번째 줄에는 서로 다른 두 정수 ui, vi (0 ≤ ui, vi < n)가 주어지며, ui와 vi가 이웃 도시임을 나타낸다.
출력
트리토피아의 도시를 나열한 순서를 나타내는 n개의 정수를 공백으로 구분해 한 줄에 출력한다. 이 순서대로 선거 결과를 발표할 때 받는 불만의 수가 최소가 되어야 한다. 최적인 순서가 여러 개라면 그중 아무거나 출력해도 된다.