406806: GYM102562 G Super Glue

Mickey is a very cheeky boy who recently found two interesting items. The first item is a special type of glue - called SuperGlue and the other one is a very rare rooted tree. The tree itself is binary, which means that all of its nodes are leafs or either having two sons, where a leaf is a node without any sons. Moreover, the tree is that interesting such that it is fully balanced. A tree is fully balanced when:

where $$$l_i$$$ and $$$l_j$$$ are any two leafs in the tree. By $$$dist(i, j)$$$ we mean the distance from node $$$i$$$ to node $$$j$$$.

Mickey was wondering a lot how to combine those two items, and in the end, he decided to take a subtree from the tree (which was not the tree itself) and to glue this one to a leaf which is not part of it. Time flew and Mickey forgot what he has done but now he wants to revert the tree to its original state!

The first line of the input will contain the number of nodes $$$N \leq 15*10^5$$$ of the resulting tree.

The following $$$N-1$$$ lines will each contain an edge between two nodes of the resulting tree.

You should output three numbers on the same line:

• the node representing the root of the original tree.
• the node representing the root of the subtree that was glued; this subtree is defined based on the original root found in the above bullet.
• the node to which the subtree has to be glued to retrieve the original tree.

3
1 2
1 3

2 3 2

The tree from the input is:

The original tree is as follows: