시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 6 2 2 33.333%

문제

Given a tree, add as many edges as possible so that the resulting graph is a cactus graph.

A cactus graph is a graph where each edge is contained in at most one simple cycle. This graph may not contain self-loops or parallel edges.

입력

The first line contains an integer $N$, the size of the tree ($1 \le N \le 200\,000$).

Each of the next $N - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$, $u \neq v$), indicating that there is an edge between nodes $u$ and $v$. It is guaranteed that the resulting graph is a tree.

출력

On the first line, output $K$, the maximum number of edges that can be added to the graph. On each of the next $K$ lines, output two integers $a$ and $b$ ($1 \le a, b \le N$, $a \neq b$), indicating that you are going to add an edge between nodes $a$ and $b$. The resulting graph must be a cactus graph.

If there are several solutions with the maximum possible $K$, output any one of them.

예제 입력 1

6
6 4
3 1
3 6
4 5
2 3

예제 출력 1

2
2 1
3 5