작업 공정

한 회사의 일은 조직도의 아래에서 위로 진행된다. 말단 직원들이 먼저 자기 작업을 처리하고, 어떤 직원은 자기 아래에 있는 모든 직원의 작업이 끝난 뒤에야 작업을 시작할 수 있다. 사장이 자기 작업을 마치면 전체 작업이 끝난다. 모든 직원의 작업은 시작부터 완료까지 정확히 1의 시간이 걸린다.

각 직원은 사장을 제외하고 직속 상사가 정확히 한 명 있다. 회사는 일부 직원을 줄이려 한다. 줄어든 직원의 작업은 남아 있는 직원 중 누군가가 대신 맡을 수 있으며, 한 직원은 같은 시간에 하나의 작업만 할 수 있다. 다른 직원의 작업을 대신 맡는 것은 자유롭지만, 직원을 줄이기 전보다 전체 작업 완료 시간이 길어지면 안 된다.

직속 상사 관계가 주어질 때, 원래 필요한 최소 작업 완료 시간과, 그 시간을 유지하면서 줄일 수 있는 직원 수의 최댓값을 구하라.

첫째 줄에 직원 수를 나타내는 정수 N(1 <= N <= 100,000)이 주어진다. 다음 N개의 줄에는 차례대로 1번, 2번, ..., N번 직원의 직속 상사 번호가 주어진다. 사장의 경우에는 -1이 주어진다.

첫째 줄에 모든 직원이 있을 때 필요한 최소 작업 완료 시간을 출력한다. 둘째 줄에 그 시간을 유지하면서 줄일 수 있는 직원 수의 최댓값을 출력한다.

한 가지 최적 진행은 다음과 같이 볼 수 있다.

• 시간 0-1: 남아 있는 네 명의 직원이 동시에 4, 5, 6, 7번 직원의 작업을 수행한다.
• 시간 1-2: 다음에 두 명의 직원이 2, 3번 직원의 작업을 수행한다.
• 시간 2-3: 마지막으로 1번 직원의 작업을 수행한다.