잃어버린 순수

시간 제한1초메모리 제한1024 MB

요약

트리가 주어질 때 모든 정점이 적어도 하나의 사이클에 속하도록 간선을 최소로 추가하고 그 간선들을 출력한다.

난이도: 보통10점 중 7점
유형: 트리, 그리디, DFS
정답자: 아직 제출이 없습니다

문제

$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)$ 를 공백으로 구분하여 출력한다.

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

예제2

예제 1
입력
```
5
1 4
1 2
1 3
1 5
```
예상 출력
```
2
2 4
3 5
```
예제 2
입력
```
7
1 3
2 3
3 4
4 5
5 6
5 7
```
예상 출력
```
2
1 6
2 7
```