네트워크

바이트랜드 정부는 나라를 인터넷에 연결하기로 했다. 모든 국민이 프로그래밍 대회에 참가하고 귀여운 고양이 영상을 볼 수 있게 하려는 것이다. 정부는 인터넷 낙관주의 주식회사에 바이트랜드의 컴퓨터 $n$대를 모두 연결하는 일을 맡겼다. 회선은 컴퓨터 두 대를 직접 잇는 방식으로 놓았고, 어느 두 컴퓨터든 회선을 몇 개 거쳐 서로 연결된다.

바이트랜드는 부유한 나라가 아니라서 비용을 줄이려고 망을 트리 모양으로 만들었다. 즉 컴퓨터를 직접 잇는 회선은 정확히 $n-1$개다. 한참 뒤에야 이 구조에 큰 약점이 있다는 사실을 알았다. 회선 하나만 끊어져도 망이 두 조각으로 나뉘어 서로 통신하지 못하는 컴퓨터가 생긴다.

바이트랜드의 망은 적어도 회선 하나가 끊어지는 상황은 견뎌야 한다. 트리 모양의 망이 주어질 때, 어떤 회선 하나가 끊어져도 모든 컴퓨터가 여전히 서로 연결되어 있도록 새로 놓아야 하는 회선의 최소 개수를 구하고 그 회선을 출력하는 프로그램을 작성하시오.

첫째 줄에 바이트랜드의 컴퓨터 개수 $n$이 주어진다 ($n \ge 3$). 컴퓨터에는 $1$번부터 $n$번까지 번호가 붙어 있다.

다음 $n-1$개 줄에는 정수 $a$와 $b$가 주어지며 ($1 \le a, b \le n$, $a \ne b$), 컴퓨터 $a$와 $b$를 직접 잇는 회선을 뜻한다. 주어지는 회선은 트리를 이룬다.

첫째 줄에 새로 놓아야 하는 회선의 최소 개수 $k$를 출력한다. 다음 $k$개 줄에는 새로 이을 컴퓨터 두 대의 번호 $a$와 $b$를 출력한다 ($1 \le a, b \le n$, $a \ne b$).

최소 개수를 만족하는 회선 집합은 여러 가지이므로, 다음 규칙으로 정한 집합 하나만 정답으로 인정한다.

1. 회선이 두 개 이상 붙어 있는 컴퓨터 중 번호가 가장 작은 것을 $r$이라 하고, 트리의 뿌리를 $r$로 잡는다.
2. $r$에서 깊이 우선 탐색을 한다. 각 컴퓨터에서는 이웃을 번호가 작은 쪽부터 방문한다. 회선이 하나만 붙어 있는 컴퓨터를 탐색이 처음 도달한 순서대로 $l_1, l_2, \dots, l_L$이라 한다.
3. $h = \lceil L/2 \rceil$로 두고, $i = 1$부터 $L-h$까지 각각 쌍 $(l_i, l_{i+h})$을 고른다.
4. $L$이 홀수면 쌍 $(l_h, l_1)$을 하나 더 고른다.
5. 고른 쌍의 개수가 $k$이고, 그 값은 $\lceil L/2 \rceil$이다.
6. 각 쌍은 번호가 작은 쪽을 먼저 쓰고, 쌍 전체를 사전순으로 오름차순 정렬해 한 줄에 하나씩 출력한다.

이 규칙으로 고른 쌍은 이미 놓여 있는 회선과 겹치지 않는다.