PT07B - The Easiest Problem

You are given an unweighted, undirected tree T. We say T is special iff it has this property:

"All nodes of degree greater than or equal to 3 are surrounded by at most two nodes of degree two or greater."

Finding maximal size subtree of this tree so that it's a special tree.

Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 106). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).

Output

At the first line, output number of nodes in the optimal subtree you found. Next lines, print all edges belong to that subtree, each line contains a pair u v means an edge between node u and node v.

Example

Input:
5
1 2
2 3
2 4
2 5

Output:
5
1 2
2 3
2 4
2 5

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:0.100s-1.243s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber

hide comments
2013-06-04 14:49:43 linzequn
There is something wrong about the check program.I get WA until I print the edges as the order they inputed.However the problem didn't require this!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.