30028번 - 잃어버린 순수 스페셜 저지

문제

$N$개의 정점과 $N-1$개의 간선으로 이루어진 트리가 있다. 각각의 정점은 1,2,ドル\cdots ,N$번으로 번호가 매겨져 있다. 이 트리에 간선을 최소한으로 추가해서 모든 정점이 적어도 하나의 사이클에 포함되게 만들어 보자. 단, 자기 자신을 잇는 간선은 추가할 수 없고, 완성된 그래프의 임의의 두 정점 사이에는 간선이 최대 한 개 존재해야 한다.

모든 정점이 적어도 하나의 사이클에 포함되게 만들기 위해 추가해야 하는 간선의 최소 개수와, 각각의 간선이 잇는 두 정점의 번호를 구해보자.

입력

첫째 줄에 정수 $N(3\le N\le 100,円 000)$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 각 간선이 잇는 두 정점의 번호 $u,v(1\le u,v\le N;u\neq v)$가 공백으로 구분되어 주어진다.

출력

첫째 줄에 추가해야 하는 간선의 최소 개수 $M$을 출력한다.

둘째 줄부터 $M$개의 줄에 추가된 각 간선이 잇는 두 정점의 번호 $u,v(1\le u,v\le N;u\neq v)$를 공백으로 구분하여 출력한다.

가능한 정답이 여러 가지라면 아무 것이나 하나 출력한다.

제한

힌트