진화 2

생명체의 진화 과정을 다루는 연구를 진행하고 있다. 최초 생명체를 제외한 모든 생명체는 기존에 존재하던 생명체가 진화하여 새롭게 탄생한다. 이때, 기존에 존재하던 생명체를 부모 생명체, 새롭게 탄생한 생명체를 자식 생명체라고 정의한다.

$N$개의 각 생명체에는 $0$ 이상 $N-1$ 이하의 서로 다른 탄생 번호가 붙어 있다. 탄생 번호는 생명체가 탄생한 순서대로 부여된다. 이에 따라, 부모 생명체의 탄생 번호는 자식 생명체의 탄생 번호보다 작으며, 최초 생명체의 탄생 번호는 $0$이다.

생명체들이 진화를 통해 탄생하는 과정은 생명체를 정점으로, 진화 과정을 부모 생명체와 자식 생명체를 잇는 간선으로 나타내고, 최초 생명체를 루트로 한 트리 구조로 표현할 수 있다. 이러한 트리를 진화 트리라고 부르자.

예를 들어, 아래 그림은 탄생 번호가 0인 생명체가 진화해 탄생 번호가 1, 2인 생명체가 탄생하고, 탄생 번호가 1인 생명체가 진화해 탄생 번호가 3, 4, 5인 생명체가 탄생하고, 탄생 번호가 2인 생명체가 진화해 탄생 번호가 6인 생명체가 탄생하고, 탄생 번호가 5인 생명체가 진화해 탄생 번호가 7, 8인 생명체가 탄생하는 과정을 표현한 진화 트리이다. 아래 그림에서 트리의 각 정점에는 해당하는 생명체의 탄생 번호가 적혀 있다.

하지만 아뿔싸, 여러분의 소중한 진화 트리에 조영욱 코치가 커피를 쏟았다. 커피를 쏟은 이후, 진화 트리의 형태와 최초 생명체는 식별할 수 있으나, 최초 생명체를 제외한 각 생명체의 탄생 번호는 식별할 수 없게 되었다.

조영욱 코치는 급한 대로 각 생명체에 임시 번호를 매겼다. 최초 생명체의 임시 번호는 0으로 매겼고, 최초 생명체를 제외한 다른 $N-1$개의 생명체에는 각각 $1$ 이상 $N-1$ 이하의 서로 다른 번호를 임의로 매겼다. 각 생명체의 임시 번호는 탄생 번호와 다를 수도, 같을 수도 있다. 또한, 탄생 번호와는 달리 부모 생명체의 임시 번호가 자식 생명체의 임시 번호보다 작다는 보장은 없다.

예를 들어, 아래 그림은 위에서 예시로 든 진화 트리와 같으나, 트리의 각 정점에는 해당하는 생명체의 임시 번호가 적혀 있다.

다행히도 진화 트리의 백업본이 조영욱 코치의 노트북에 저장되어 있었다. 하지만 백업본은 암호화되어 있고, 조영욱 코치는 백업본의 암호를 기억하지 못하고 있다. 대신, 조영욱 코치는 백업본의 백업 프로그램을 사용할 수 있다.

백업 프로그램에는 두 생명체의 임시 번호를 입력하면, 두 생명체 중 어느 생명체의 탄생 번호가 더 작은지 알려주는 기능이 있다. 이 기능을 너무 많이 사용한다면 조영욱 코치의 성능 낮은 노트북이 고장날 수도 있으므로, 여러분은 조영욱 코치를 도와 적은 횟수의 질문으로 진화 트리의 모든 생명체의 탄생 번호를 복구하는 코드를 작성해야 한다.

문제

제한