Binarytreefication

$N \le 2\,000$을 만족하는 노드 $N$개의 트리 $T$가 주어진다. 다음의 조건을 만족하는 트리 $T'$를 구성하여 출력하자.

• $T'$의 크기를 $M$이라 하자. $M$은 $N$ 이상 $22\,000$ 이하여야 한다. 즉, $N \le M \le 22\,000$이여야 한다.
• $T'$은 이진 트리이여야 한다. 즉, $T'$의 모든 노드는 $3$개 이하의 다른 노드들과 연결되어야 한다.
• $\text{dist}(u, v)$를 $T$에서 $u$번 노드와 $v$번 노드 사이의 거리로 정의하자. 비슷하게, $T'$에 대해서 $\text{dist}'(u, v)$를 $u$번 노드와 $v$번 노드의 거리로 정의하자.
• $1 \le u, v, p, q \le N$에 대해 $\text{dist}'(u, v) = \text{dist}'(p, q)$이면 $\text{dist}(u, v) = \text{dist}(p, q)$이여야 한다.

첫째 줄에 $N$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐 $T$의 각 간선의 양 끝점의 번호가 한 줄에 공백으로 구분되어 주어진다.

첫째 줄에 $M$을 출력한다.

둘째 줄부터 $M-1$개의 줄에 걸쳐 $T'$의 각 간선의 양 끝점의 번호를 한 줄에 공백으로 구분하여 출력한다.

• $2 \le N \le 2\,000$

트리는 임의의 두 정점 사이의 단순 경로가 유일하게 존재하는 연결 그래프를 말한다.