Problem G
The Tree Root
Input: standard input
Output: standard output
Time Limit: 4 seconds
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
Sample Output