The Tree Root

Tree is an important data structure. Searching is a basic operation in any data structure. In a tree searching mainly depends on its height. Consider the following three trees. If you observe carefully, you will see that all trees are same except different nodes are used as roots. Here the height of the tree varies with the selection of the root. In the 1st tree root is ’2’ and height is 3. In 2nd one root is ’1’ and height is 2. And in last one root is ’4’ and height is 4. We will call ’1’ best root as it keeps the tree with the least possible height and ’4’ worst root for the opposite reason. In this problem, you have to find out all best roots and worst roots for a given tree. Input Each dataset starts with a positive integer N (3 ≤ N ≤ 5000), which is the number of nodes in the tree. Each node in the tree has a unique id from 1 to N. Then successively for each i’th node there will be a positive integer K[i] following id of K[i] nodes which are adjacent to i. Input is terminated by EOF. Output For each dataset print two lines. In the 1st line show all the best roots in ascending order and in next line show all worst roots in ascending order. See sample output for exact format. Sample Input 7 223 3167 3145 13 13 12 12 Sample Output Best Roots : 1 Worst Roots : 4 5 6 7