코코아와 마법사의 돌

코코아는 국내 최대의 마법학교 "래빗 하우스"에서 마법을 공부하는 견습 마법사다. 코코아는 정식 마법사로 승급하기 위한 시험을 치르게 되었다. 이 시험을 통과하면 마법사의 돌을 받아 정식 마법사가 된다. 시험 담당자 리제가 코코아에게 다음 문제를 냈다.

1부터 $N$까지 번호가 매겨진 $N$개의 정점으로 이루어진 트리가 주어질 때, 간선을 $\left\lfloor \frac{N}{5} \right\rfloor$개 이하로 추가해서 그래프의 지름을 10 이하로 만들어라.

코코아가 어떤 간선을 추가해야 하는지 알려주자.

첫째 줄에 트리에 속한 정점의 개수 $N$이 주어진다 ($1 \le N \le 1000$).

둘째 줄부터 $N$번째 줄까지 두 정수 $u$, $v$가 공백으로 구분되어 한 줄에 하나씩 주어진다. 이는 정점 $u$와 $v$ 사이에 트리의 간선이 있다는 뜻이다 ($1 \le u, v \le N$; $u \neq v$).

첫째 줄에 추가할 간선의 개수 $M$을 출력한다 ($0 \le M \le \left\lfloor \frac{N}{5} \right\rfloor$).

다음 $M$개의 줄에는 두 정수 $u$, $v$를 공백으로 구분하여 출력한다. 이는 정점 $u$와 $v$ 사이에 새 간선을 추가한다는 뜻이다 ($1 \le u, v \le N$; $u \neq v$).

간선을 추가한 그래프에는 같은 두 정점을 잇는 간선이 둘 이상 있어서는 안 되며, 모든 간선은 서로 다른 두 정점을 이어야 한다.

그래프의 지름은 임의의 두 정점 사이 최단 거리 중 가장 큰 값이다. 정점 $A$와 $B$ 사이의 최단 거리는 $A$와 $B$를 양 끝점으로 하는 단순 경로들 가운데 간선 수가 가장 적은 경로의 간선 수다.