Tree Height and Width

Place a binary tree on a grid whose rows and columns are numbered, using the following rules.

1. Nodes on the same level are placed in the same row.
2. Each column contains at most one node.
3. Every node in a node's left subtree is placed in a column to the left of that node, and every node in its right subtree is placed in a column to the right of that node.
4. Between the leftmost and rightmost columns that contain nodes, there is no completely empty column.

After placing the tree this way, the width of a level is defined as the rightmost column number among nodes on that level minus the leftmost column number among nodes on that level, plus 1. The root is on level 1, and the level number increases by 1 each time you move down the tree.

The diagram below shows one binary tree placed by these rules. The width of level 1 is 1, the width of level 2 is 13, the widths of levels 3 and 4 are both 18, the width of level 5 is 13, and the width of level 6 is 12.

Given a binary tree, compute the level with the greatest width and that width. If multiple levels have the same greatest width, choose the smallest level number. In the diagram above, levels 3 and 4 both have width 18, so the answer is level 3 and width 18.

Write a program that prints the widest level of the given binary tree and the width of that level.

The first line contains the number of nodes N, where 1 <= N <= 10,000.

Each of the next N lines contains a node number, the number of its left child, and the number of its right child, in that order. Node numbers are from 1 to N. If a child does not exist, its number is given as -1.

Print the level with the greatest width and the width of that level, in that order. If multiple levels have the greatest width, print the smallest such level number.

This problem is also known by the title "Width of a Binary Tree".