32214번 - 코코아와 마법사의 돌 스페셜 저지

문제

코코아는 국내 최대의 마법학교인 "래빗 하우스"에서 마법을 공부하고 있는 견습 마법사이다! 코코아는 이번에 정식 마법사로 승급하기 위한 시험을 치르게 되었는데, 이 시험을 통과한다면 마법사의 돌을 받아 정식 마법사가 될 수 있다. 시험장에 들어온 그녀에게, 시험 담당자인 리제는 다음과 같은 문제를 냈다:

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

코코아를 도와 어떤 간선을 추가해야 하는지 알려주자!

입력

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

둘째 줄부터 $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$를 끝점으로 가지는 모든 단순 경로들에 대해, 경로 안에 속한 간선의 개수 중 가장 작은 값을 의미한다.