Description

The government of Byteland has decided that it is time to connect their little country to the Internet, so that all citizens can participate in programming competitions and watch videos of cute cats. When it was time to build the network backbone of the country, they assigned the company Internet Optimists Inc. with connecting all the n computers of Byteland. The connections were made as direct links between pairs of computers in such a way that any pair of computers are connected by a sequence of links.

Input

The first line of input contains a positive integer n(N>=3), the number of computers in Byteland. For simplicity, all computers are numbered from 1 to n. Each of the following n-1 lines contains a pair of integers a and b (1<=a,b<=n,a<>b) that describes a direct link between computers a and b.

Output

In the first line of output your program should write an integer k, the minimal number of links that should be added to the network. In each of the following k lines your program should write a pair of integers a and b (1<=a,b<=N,a<>b)  that denote the numbers of computers that should be connected by a link. The links can be written in any order. If there is more than one solution, your program should output any one of them.

Sample Input

Sample Output

Hint

 N<=500 000

Source