eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Plunder & Flee

Plunder & Flee

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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.

Входные данные

The first line of the input file contains integer n (2n1000), 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 a_i and b_i (1a_i, b_in). The workstations are identified with natural numbers ranging from 1 to n.

Выходные данные

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.

Пример

Входные данные #1
3
1 2
2 3
Выходные данные #1
1
1 3
Источник 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17