지문이 문제를 정의하는 것보다 DB 모델을 설명하는 데에 집중되어 있어 이해하는 데에 너무 힘들었어서, 문제 푸는 데에 필요한 부분만 PS적인 용어를 사용하여 요약해 보았습니다.

노드 N(<=10만) 개 이하의 트리가 주어집니다. 정점에는 1번부터 N번까지 번호가 매겨져 있고, 이 트리를 다음과 같은 규칙으로 방문해야 합니다.

• 루트 노드 S부터 깊이 우선으로 방문합니다.
• 자식 노드가 여럿이면, 번호가 가장 작은 노드부터 방문합니다.
• 트리 순회 시 글로벌한 카운트 변수를 두고, 각 노드를 방문하는 시점을 그 노드의 left, 방문을 마치고 나가는 시점을 right에 기록합니다. 카운트 변수는 1부터 시작하며, 기록할 때마다 1 증가합니다.

입력의 첫 번째 줄은 N이고, 두 번째 줄부터 N개의 줄에는 각각 첫 수로 정점 번호가 나오고 이후 -1이 주어지기 전까지 이 정점에 연결된 노드들이 모두 주어집니다. 마지막 줄에는 S가 주어집니다.

이 트리를 위의 규칙으로 방문한 결과를 1번부터 N번까지 차례대로 (노드 번호) (그 노드의 left) (그 노드의 right)로 출력하면 됩니다.