Problem J
Bridge Removal

Countless programming contest problems involve houses and roads connecting pairs of houses in a way that guarantees there is exactly one path between any two houses. That is, if we view the road network as a graph where vertices are houses and edges are roads directly connecting two houses, then many problems have this graph being a tree.

Unfortunately for you, the city planner, your predecessor posed the problem of designing the road network for your city as such a contest problem and is now using this solution! The problem with such road networks is that if any single road/edge becomes unusable then there are locations that can no longer reach each other.

This is unacceptable. Your task is to add new roads to ensure that any two houses can still reach each other even if a single road in your road network becomes unusable. Naturally, this should be done while adding the fewest roads possible. Note, it is acceptable to add a 2nd road between two locations even if a road exists between them already (see the first sample input and output).

Figure 1: Illustration of the sample cases. The solid edges are part of the original tree and the dashed edges are one possible correct solution.

Input

The first line of input contains a single integer $N$ ($2 \leq N \leq 200\, 000$). Then $N-1$ lines follow, the $i$’th such line containing two integers $u_i, v_i$ ($1 \leq u_i, v_i \leq N$ with $u_i \neq v_i$) describing a road that directly connects $u_i$ to $v_i$. You are guaranteed there is exactly one way path between any two houses. That is, when the input is viewed as a graph it is just a single tree.

Output

The first line of output contains a single integer $R$ indicating the minimum number of new roads that need to be added. Each of the next $R$ lines describes a new road, the $j$’th such line containing two integers $u_j, v_j$ indicating a new road between houses $u_j$ and $v_j$ should be built. If there are multiple possible solutions with the minimum value of $R$, you may output any.

4
1 2
2 3
2 4

2
1 2
3 4

6
1 3
2 3
3 4
4 5
4 6

2
2 5
6 1