거리 코드

여러분의 과제는 인코더와 디코더, 두 가지 방식으로 쓸 수 있는 프로그램을 만드는 것이다.

인코더는 $n$개의 노드로 이루어진 트리를 받아 모든 노드를 트리에서 제거한다. 매 단계마다 인코더는 현재 트리에서 임의의 리프 노드 하나를 제거할 수 있다.

디코더는 인코더가 연속으로 제거한 노드 사이의 거리 목록을 받는다. 디코더는 이 목록으로 원래 트리의 구조를 복원해야 한다. 디코더가 만드는 트리는 원래 트리와 같은 구조(정확히는 원래 트리와 동형)이기만 하면 어떤 트리든 된다.

첫 줄에는 정수 $t$가 주어진다. $t$는 1(인코더) 또는 2(디코더)이다.

둘째 줄에는 트리의 노드 개수 $n$이 주어진다. 노드는 $1,2,\dots,n$으로 번호가 매겨져 있다.

$t=1$이면 이어서 트리를 설명하는 $n-1$개의 줄이 주어진다. 각 줄에는 정수 $a$와 $b$가 주어지며, 이는 노드 $a$와 노드 $b$ 사이에 간선이 있다는 뜻이다.

$t=2$이면 $n-1$개의 정수가 한 줄에 주어진다. 이 정수들은 인코더가 연속으로 제거한 노드 사이의 거리이다.

$t=1$이면 인코더는 $1,2,\dots,n$의 순열을 출력해야 한다. 이 순열은 노드가 트리에서 제거된 순서이다.

$t=2$이면 디코더는 트리의 구조를 설명하는 $n-1$개의 줄을 출력해야 한다.