dlaud5379   8달 전

(Kagi Translate로 번역한 텍스트를 다듬었습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

은하는 최근에 대형 소프트웨어 기업에서 일을 시작했다. 이 회사의 조직도는 트리 형태이며, 사장을 제외한 모든 직원은 정확히 한 명의 직속 상사를 가진다. 회사는 여러 개의 팀으로 이루어져 있는데, 각 사원마다 그 사원의 서브트리에 속한 모든 직·간접 부하(존재할 경우)가 한 팀에 속한다. 즉, 한 팀 안에도 그 팀을 이루는 다른 팀이 여러 개 있을 수 있다. M사를 예로 들어서 설명하면 오피스 제품군을 담당하는 팀이 있고 그 아래에 워드 팀, 엑셀 팀이 있는 것과 마찬가지이다. 은하가 있는 조직도를 보면 한별이는 골드와 은하의 상사이고, 은하는 봄의 상사, 골드는 브론즈와 실버의 상사이다. 이 경우 한별이, 골드, 은하, 봄, 브론즈, 실버가 한 팀, 은하, 봄이 한 팀, 브론즈, 실버, 골드가 한 팀을 이룬다.

사무실은 길이가 충분히 길지만 폭은 매우 좁기 때문에 자리를 한 줄로만 배치할 수 있다. 사장은 맨 왼쪽 자리에 있으며, 다음을 만족하도록 직원을 배치하고자 한다.

  • 모든 직원의 직속 상사는 자신보다 왼쪽에 있어야 한다.
  • 각 팀의 구성원들은 연속된 자리를 차지해야 한다. (즉, 서로 붙어 있어야 한다.)

은하의 조직도를 예시로 들면, 한별이, 골드, 브론즈, 실버, 은하, 봄의 순서가 조건을 만족한다.

은하는 이번 분기에 성과를 내고 싶어 한다. 회사의 조직도가 주어졌을 때 직원들의 배치 순서를 결정하는 프로그램을 작성하여라.

입력

첫째 줄에 회사의 직원 수 N이 주어진다. 모든 직원들에게는 1 이상 N 이하의 정수 사번이 부여되어 있으며, 사장의 사번은 1이다.

둘째 줄부터 N-1개의 줄에 걸쳐 회사의 조직도가 주어진다. 각 줄마다 두 정수 W1, W2가 주어지며, 이는 W1번 직원이 W2번 직원의 직속 상사라는 의미이다.

출력

1 이상 N 이하의 정수 N개를 문제에서 요구하는 순서대로 한 줄로 출력한다. 가능한 배치가 여러 개일 경우 사전순으로 가장 앞에 오는 것을 출력한다.

서로 다른 두 자리 배치 A와 B에 대해 첫 자리부터 비교해서 두 배치가 처음으로 달라지는 위치 i가 존재하며, 이때 Ai < Bi일 경우 사전순으로 A가 B보다 앞선다고 한다. 예를 들어 [1, 3, 4, 6, 7, 2, 5]는 [1, 3, 5, 2, 4, 6, 7]보다 앞선다.

제한

  • 1 ≤ N ≤ 200,000

힌트

예제 입력 1에서 1번, 2번, 5번, 4번, 3번, 6번 직원은 각각 한별이, 은하, 봄, 골드, 브론즈, 실버에 해당한다.

댓글을 작성하려면 로그인해야 합니다.