Mirror Tree?
MIRROR-TREE-CHECK (MT Check) is a classic CAPTCHA at the gates of the Link-Cut planet system. It involves simply checking a tree for mirror symmetry.
Here is the process of mirroring a tree:
Choose two vertices and (henceforth referred to as mirroring with respect to the - path).
Hang the tree from vertex .
For each vertex on the path from to , create a copy of each of the children's subtrees of a vertex and connect them to the same vertex if that vertex's subtree does not contain .
We will denote this process as , which means mirroring tree with respect to the - path.
Here is an example of mirroring a given tree with respect to the path between the -st and -th vertex:
The given tree | The new tree, where blue vertices denote the vertices which were added |
A tree is called mirrored if we can choose another tree and two of its vertices and such that tree and tree are similar.
We consider two trees to be similar if we can change the numbering of the vertices in both trees such that the sets of edges of these two trees are identical.
You were prepared for this task, but the evil Chmyaks surprised you with a new trick. By casting a spell on the gates, he added one leaf to the input tree. Now the gates won't let anyone through.
You were almost in despair when suddenly the wizard Frusi appeared to help you. Frusi possesses strong magic and can try to break the spell, but to do so, he will have to remove the leaf that Chmyaks added. Checking each leaf would take too long and require too much mana (even Frusi doesn't have that much). Fortunately, our wizard recognized the spell and told you about a side effect: the tree before the leaf was added was definitely mirrored.
Frusi is now preparing his spells, and your task is to find all potential leaves that Chmyaks could have added (i.e., all such leaves, after removing which the tree will become mirrored, henceforth referred to as bad vertices) or tell that Frusi has made a mistake and there are no such leaves.
Input
The first line contains one integer — the number of vertices in the tree. Each of the next lines contains two integers and — the edge between and . It is guaranteed that these edges form a tree.
Output
In the first line, output the number of such bad leaves (if there are no such leaves — output ).
In the second line, output all bad leaves, sorted in ascending order or do not output anything if there are no such leaves.
Examples
Scoring
( points): each vertex is connected with at most 2 others (the tree is a bamboo);
( points): at most one vertex connected more than with 1 other vertex (the tree is a hedgehog);
( points): ;
( points): ;
( points): ;
( points): no additional constraints.