Network

The government of Byteland decided to connect the country to the Internet, so that every citizen can enter programming contests and watch videos of cute cats. It gave Internet Optimists Inc. the job of connecting all $n$ computers of Byteland. Each link joins two computers directly, and any two computers are connected through a sequence of links.

Byteland is not a rich country, so the company kept the cost down by building the network as a tree. There are exactly $n-1$ links between computers. Much later it turned out that this design has a serious weakness. If a single link breaks, the network falls apart and some computers can no longer talk to each other.

The network of Byteland has to survive at least one broken link. Given the tree, find the minimum number of links that have to be added so that all computers stay connected after any single link breaks, and print those links.

The first line contains the number of computers $n$ in Byteland ($n \ge 3$). The computers are numbered from $1$ to $n$.

Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), a link that joins computers $a$ and $b$ directly. The given links form a tree.

Print the minimum number of links $k$ that have to be added on the first line. On each of the next $k$ lines print two computer numbers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$) that get a new link.

Several different sets of $k$ links work, so only the set chosen by the following rule is accepted.

1. Let $r$ be the smallest numbered computer that has at least two links, and root the tree at $r$.
2. Run a depth first search from $r$. At every computer, visit the neighbours in increasing order of number. Let $l_1, l_2, \dots, l_L$ be the computers that have exactly one link, in the order the search first reaches them.
3. Let $h = \lceil L/2 \rceil$. For every $i$ from $1$ to $L-h$, choose the pair $(l_i, l_{i+h})$.
4. If $L$ is odd, choose one more pair $(l_h, l_1)$.
5. The number of chosen pairs is $k$, and it equals $\lceil L/2 \rceil$.
6. Print the smaller number of a pair first, and print all pairs sorted in increasing order, one per line.

A pair chosen by this rule never repeats a link that already exists.