21114번 - Into Cactus 스페셜 저지다국어

문제

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.

제한

힌트