## PT07B - The Easiest Problem

no tags

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
```

hide comments
 linzequn: 2013-06-04 14:49:43 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!!

 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