Hacker Kirill successfully coped with the
task that "Plunder & Flee Inc." management had set before him
last year, and he was transferred to the central office. Now he faces a new
challenge of improving the computer network in the central office. The network
consists of n workstations coupled by n–1 network
cables; each pair of workstations has at most a single connection. Information
is relayed between stations until it reaches the recipient.
Currently, the network is set up in such a
way that only a single route exists between any two stations. The solution is
cheap but it has a major shortcoming: any cable failure renders the network
inoperable.
The management asked Kirill to improve the
network using the least possible number of additional cables so as to keep the
network operational in case of a single cable failure.
Write a program that, given the network
structure, will determine the minimum number of additional cables necessary to
improve the network as described above.
Limitations
2 ≤ n ≤ 1000; 1 ≤
ai, bi ≤ n.
Input
The first line of the input file contains
integer n, the number of workstations in the network. The
following n–1 lines describe the communication links. They
contain space-delimited numbers of workstations connected by cable i:
integers ai and bi. The
workstations are identified with natural numbers ranging from 1 to n.
Output
The first line of the output file should
contain integer m, the number of additional cables. Then m
lines should follow, each consisting of a space-delimited pair of integers
denoting the numbers of newly connected stations.
Example
Input
|
Output
|
|
3
1 2
2 3
|
1
1 3
|
Input
|
Output
|
|
4
1 4
2 4
3 4
|
2
1 2
2 3
|
