침투

Ondrej와 Edward는 스파이이며 악의 조직 AQT를 무너뜨리려 한다. 이를 위해 AQT의 기지에 침투해야 한다. 기지는 $N = 100$개의 방으로 이루어진 트리로 모델링하며, 방 번호는 0부터 $N - 1$까지이다. 두 사람의 계획은 먼저 납치된 뒤 함께 만나서 작전을 실행하는 것이다. 납치되면 두 사람은 서로 다른 방에 놓이며, 상대가 어느 방에 있는지 알지 못한다. 방에 놓이면 두 사람은 자정에 탈출하여 작전을 실행하기 전에 서로를 만나려 한다.

만나는 방식은 다음과 같다. 홀수 분마다 Ondrej는 현재 방에 머무르거나 인접한 방으로 이동할 수 있다. 짝수 분마다 Edward는 현재 방에 머무르거나 인접한 방으로 이동할 수 있다.

전략은 다음과 같이 정의한다. $V(A, R, T)$는 에이전트 $A$가 자정에 방 $R$에 있었다고 가정하고, 자정 후 $T$분이 지난 지금 $A$가 있어야 하는 방을 나타낸다. 전략은 위 조건을 따라야 한다. 두 에이전트는 시각 $t(o, e)$에 만나며, 이는 $V(\text{Ondrej}, o, t(o, e)) = V(\text{Edward}, e, t(o, e))$가 처음 성립하는 시각이다.

Ondrej와 Edward는 시작 방 사이의 거리에 비해 가능한 한 빨리 만나려 한다. 거리 $d(o, e)$는 $e$에서 $o$까지 도달하기 위해 반드시 지나야 하는 복도의 최소 개수이다. 서로 다른 모든 방 쌍 $o$, $e$에 대해 $\frac{t(o,e)}{d(o,e)}$의 최댓값을 최소로 만드는 전략을 찾아라.

입력의 첫 줄에는 $N$이 주어진다($N = 100$). $N$의 값이 100이 아니면 즉시 프로그램을 종료하라.

이어지는 $N - 1$개의 줄에는 양방향 복도로 연결된 두 방의 번호가 공백으로 구분되어 주어진다.

먼저 시작 방마다 기록하는 항목 수인 양의 정수 $T$를 출력한다. $T \le 1440$을 만족해야 하며, 그렇지 않으면 점수를 받지 못한다.

그다음 Ondrej의 전략, Edward의 전략을 차례로 출력한다. 각 전략은 $N$줄로 이루어지며, $n$번째 줄(0부터 시작)은 방 $n$에서 출발한 에이전트의 경로이다. 각 줄에는 시각 $1, 2, \dots, T$에 에이전트가 있어야 할 방 번호를 공백으로 구분하여 $T$개 출력한다.