Lost Purity

Interview

Time limit1sMemory limit1024 MB

Summary

Given a tree, add the fewest edges so that every vertex lies on a cycle, then print the endpoints of each added edge.

Level: Medium5 of 10
Topics: Tree, Greedy, DFS
Solved: No attempts yet

Problem

There is a tree with $N$ vertices and $N-1$ edges. The vertices are numbered $1,2,\cdots ,N$ . Add the fewest possible edges to this tree so that every vertex lies on at least one cycle. An edge cannot connect a vertex to itself, and the completed graph can have at most one edge between any two vertices.

Find the minimum number $M$ of edges to add, and the two endpoints of each added edge.

Input

The first line contains an integer $N$ ( $3\le N\le 100\,000$ ).

Each of the next $N-1$ lines contains two integers $u,v$ ( $1\le u,v\le N;u\neq v$ ), the endpoints of an edge, separated by a space.

Output

On the first line, print the minimum number of edges $M$ to add.

On each of the next $M$ lines, print the two endpoints $u,v$ ( $1\le u,v\le N;u\neq v$ ) of an added edge, separated by a space.

If there are multiple valid answers, print any one of them.

Examples2

Example 1
Input
```
5
1 4
1 2
1 3
1 5
```
Expected output
```
2
2 4
3 5
```
Example 2
Input
```
7
1 3
2 3
3 4
4 5
5 6
5 7
```
Expected output
```
2
1 6
2 7
```