효율적인 버스 노선 설계

Optopia 나라는 모든 것을 가능한 한 최적으로 처리하며, 나라 안의 모든 것이 이 원칙에 따라 설계되었다. 예를 들어 GPS 경로 안내가 항상 최적 경로를 찾도록 Optopia의 도로망은 임의의 두 도시 사이를 잇는 길이 정확히 하나뿐이도록 설계되어 있다.

Optopia에는 버스 노선망도 있다. 각 버스 노선은 두 도시 사이를 왕복하며, 그 사이에 있는 모든 도시에 정차한다. 최근 Optopia 시민 한 명이 현재 버스 노선망이 최적이 아니라는 사실을 밝혀냈다. 노선이 너무 많다는 것이다.

당신은 Optopia의 의뢰를 받아 이 부끄러운 실수를 바로잡아야 한다. 새 버스 노선망은 다음 두 조건을 만족해야 한다.

• 임의의 두 도시 쌍을 버스로 오갈 수 있어야 한다.
• 버스 노선의 수가 가능한 한 적어야 한다.

도시를 정점, 도로를 간선으로 하는 무방향 그래프로 나라를 모델링한다. 각 버스 노선은 양 끝 정류장인 두 도시로 나타낸다.

첫 줄에 도시의 수를 나타내는 정수 $N$ ($3 \leq N \leq 2 \cdot 10^5$)이 주어진다. 이어지는 $N-1$개의 줄에는 도로로 연결된 도시 쌍을 나타내는 정수 $u$와 $v$ ($1 \leq u,v \leq N$, $u \neq v$)가 한 줄에 하나씩 주어진다. Optopia는 연결되어 있어서, 도로망만으로 임의의 두 도시를 오갈 수 있음이 보장된다.

첫 줄에 최적의 버스 노선 수 $M$을 출력한다. 이어서 $M$개의 줄에 $i$번째 버스 노선의 양 끝 정류장 $a_i$와 $b_i$ ($1 \leq a_i, b_i \leq N$)를 공백으로 구분하여 출력한다.