{"raw_statement":[{"iden":"statement","content":"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 #cf_span(class=[tex-font-style-underline], body=[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 #cf_span(class=[tex-font-style-underline], body=[fully balanced]). A tree is #cf_span(class=[tex-font-style-underline], body=[fully balanced]) when: \n\n \n\n where $l_i$ and $l_j$ are any two leafs in the tree. By $d i s t (i, j)$ we mean the distance from node $i$ to node $j$.\n\nMickey 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! \n\nThe first line of the input will contain the number of nodes $N <= 15 * 10^5$ of the resulting tree. \n\nThe following $N -1$ lines will each contain an edge between two nodes of the resulting tree.\n\nYou should output three numbers on the same line: \n\nThe tree from the input is: \n\nThe original tree is as follows: \n\n"},{"iden":"input","content":"The first line of the input will contain the number of nodes $N <= 15 * 10^5$ of the resulting tree. The following $N -1$ lines will each contain an edge between two nodes of the resulting tree."},{"iden":"output","content":"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.  If there exist multiple solutions, output any of them."},{"iden":"note","content":"The tree from the input is: The original tree is as follows: "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 1000 $.  \nLet $ N = \\{1, 2, \\dots, n\\} $ be the set of nut sizes.  \nLet $ B = \\{1, 2, \\dots, n\\} $ be the set of bolt sizes.  \nThere exists a unique bijection $ \\sigma: N \\to B $ such that nut $ i $ matches bolt $ \\sigma(i) $.\n\n**Constraints**  \n1. At most $ 5n \\log_2 n $ comparison queries may be made.  \n2. Each query: output `? i j` to compare nut $ i $ and bolt $ j $, receive one of:  \n   - `<` if $ i < j $,  \n   - `>` if $ i > j $,  \n   - `=` if $ i = j $.  \n\n**Objective**  \nDetermine the permutation $ p = (p_1, p_2, \\dots, p_n) $ such that $ p_i = \\sigma(i) $, i.e., nut $ i $ matches bolt $ p_i $.  \nOutput `! p_1 p_2 ... p_n` and terminate.","simple_statement":"Steven has n nuts and n bolts, each numbered 1 to n.  \nHe can compare one nut and one bolt to find if the nut is bigger, smaller, or matches the bolt.  \nHe must match each nut to exactly one bolt using at most 5n log₂n comparisons.  \nOutput the matching for each nut (nut i matches bolt p_i).","has_page_source":false}