Company
시간 제한1초메모리 제한1024 MB
각 부분 트리가 연속된 구간을 차지해야 하는 조건에서 사원들의 사전순으로 가장 작은 배치를 구한다.
문제
Ели започна работа в голяма софтуерна компания. Йерархията в компанията има дървовидна структура, като всеки човек (освен баш шефът) има точно по един пряк началник. Компанията е разделена на екипи, като един програмист с всичките си преки и непреки подчинени (ако има такива) се счита за един екип. Това означава, че един екип може да се състои от няколко други такива. За пример ще дадем компания като Майкрософт, където има екип, който се занимава с Office, който от своя страна се състои от екипи, които се занимават с Word, Excel, и т.н. В случая на Ели, например, Станчо е шеф на Пешо и Ели, Ели е шеф на Крис, а Пешо е шеф на Гошо и Тошо. Така Станчо, Пешо, Ели, Крис, Гошо и Тошо образуват един екип. Също така Ели и Крис са един екип, а Пешо, Тошо и Гошо са друг екип.
Фирмата има много дълъг, но за съжаление тесен офис, в който има място само за един ред от компютри. Шефът на фирмата е заел най-левия от тях и иска да разпредели програмистите по такъв начин, че:
- Прекият началник на всеки програмист да се намира наляво от него.
- Членове на всеки от екипите да заемат непрекъсната последователност от компютри (тоест да са един до друг).
Ако вземем примера, който дадохме по-рано, едно възможно нареждане би било Станчо, Пешо, Гошо, Тошо, Ели, Крис.
Помогнете на Ели да се подмаже на шефа, като напишете програма, която по дадена структура на фирмата, определя нареждането на програмистите.
입력
На първия ред на стандартния вход ще бъде зададен броят програмисти във фирмата N. Ще представим програмистите с номера от 1 до N, включително, като 1 е шефът на фирмата (който няма пряк началник). На следващите N – 1 реда ще бъде зададена по една двойка числа W1 W2 указващи, че W1 е пряк началник на W2.
출력
На стандартния изход изведете един ред, съдържащ N цели числа между 1 и N – подредбата на програмистите в изискания ред. Ако има повече от една възможна подредба, изведете лексикографски най-малката. Наредба A е лексикографски по-малка от наредба B, ако числото на първата позиция, в която се различават е по-малко в A от това в B. Например {1, 3, 4, 6, 7, 2, 5} e по-малко от {1, 3, 5, 2, 4, 6, 7}.
제한
- 1 ≤ N ≤ 200,000
힌트
В първия пример Станчо е с номер 1, Ели с 2, Крис с 5, Пешо е с 4, Гошо е с 3, а Тошо с 6.