트리의 높이와 너비

이진트리를 행과 열 번호가 붙은 격자에 다음 규칙으로 배치한다고 하자.

1. 같은 레벨에 있는 노드는 같은 행에 놓인다.
2. 한 열에는 노드가 하나만 놓인다.
3. 어떤 노드의 왼쪽 서브트리에 있는 모든 노드는 그 노드보다 왼쪽 열에 놓이고, 오른쪽 서브트리에 있는 모든 노드는 그 노드보다 오른쪽 열에 놓인다.
4. 노드가 놓인 가장 왼쪽 열과 가장 오른쪽 열 사이에는 노드가 하나도 없는 빈 열이 없다.

이 규칙으로 트리를 그렸을 때, 한 레벨의 너비는 그 레벨에 있는 노드들 중 가장 오른쪽 노드의 열 번호에서 가장 왼쪽 노드의 열 번호를 뺀 뒤 1을 더한 값이다. 루트 노드의 레벨은 1이며, 아래로 내려갈 때마다 레벨이 1씩 증가한다.

아래 그림은 어떤 이진트리를 위 규칙에 따라 배치한 모습이다. 1레벨의 너비는 1, 2레벨의 너비는 13, 3레벨과 4레벨의 너비는 각각 18, 5레벨의 너비는 13, 6레벨의 너비는 12이다.

주어진 이진트리를 이 규칙으로 배치할 때, 너비가 가장 넓은 레벨과 그 너비를 구하라. 가장 넓은 레벨이 여러 개라면 레벨 번호가 가장 작은 것을 답으로 한다. 위 그림에서는 3레벨과 4레벨의 너비가 모두 18이므로, 답은 레벨 3과 너비 18이다.

임의의 이진트리가 주어질 때, 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 N이 주어진다. 1 <= N <= 10,000이다.

다음 N개의 줄에는 각 줄마다 노드 번호, 왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호가 차례로 주어진다. 노드 번호는 1부터 N까지이며, 자식이 없으면 해당 자식 노드 번호로 -1이 주어진다.

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 차례로 출력한다. 너비가 가장 넓은 레벨이 여러 개라면 레벨 번호가 가장 작은 것을 출력한다.

이 문제는 "이진트리의 너비"라는 제목으로도 알려져 있다.