Tree Analyses (APCS 2017-10 Advanced)

Tree Analyses

This problem concerns rooted trees. In a rooted tree with \(n\) nodes, every node has a distinct integer label from \(1\) to \(n\).

Exactly one node has no parent; it is the root. Every other node has exactly one parent. A node may have zero or more children, and a node with no children is a leaf. If the tree contains only one node, that node is both the root and a leaf.

The distance \(d(u,v)\) between two nodes \(u\) and \(v\) is the number of edges on the path connecting them.

For each node \(v\), its height \(h(v)\) is the distance from \(v\) to the farthest leaf in its subtree. Every leaf has height \(0\). Define the total height of the tree as

Given a rooted tree \(T\), find the label of its root and the total height \(H(T)\).

Input

The first line contains a positive integer \(n\), the number of nodes.

The next \(n\) lines describe nodes \(1\) through \(n\). The first integer \(k_i\) on line \(i\) is the number of children of node \(i\). It is followed by the labels of those \(k_i\) children. Adjacent integers are separated by one space.

The input is guaranteed to describe a valid rooted tree.

Output

Output two lines, each containing one integer:

• The first line contains the label of the root.
• The second line contains \(H(T)\).

Constraints

• \(1\le n\le100000\)
• There are 20 scored test cases, each worth 5 points. The score is awarded per correctly passed test case.
• The time limit for each test case is 1 second.

In the following table, \(k\) is the maximum number of children of any node.

Scoring

Sample Input 1

7
0
2 6 7
2 1 4
0
2 3 2
0
0

Sample Output 1

5
4

Sample Input 2

9
1 6
3 5 3 8
0
2 1 7
1 9
0
1 2
0
0

Sample Output 2

4
11

Source

APCS October 2017 Programming Problem 3, "Tree Analyses," also available as ZeroJudge c463.