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.
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).
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.
Input: 5 1 2 2 3 2 4 2 5 Output: 5 1 2 2 3 2 4 2 5
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!!