## 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* <= 10^{6}). 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 5Output: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 |