이진 트리

이진 트리는 노드로 이루어진 구조이고, 각 노드의 자식은 최대 두 개다. 자식 하나는 왼쪽 자식, 다른 하나는 오른쪽 자식이다. 노드 B가 노드 A의 자식이면 A는 B의 부모다. 이진 트리에서 부모가 없는 노드는 정확히 하나이며, 이 노드를 트리의 루트라고 한다. 노드 N의 높이는 루트에서 N까지 가는 경로에 놓인 간선의 개수다. 루트의 높이는 0이다.

트리에 있는 모든 노드의 높이를 구하라. 노드는 1부터 n까지의 정수로 구분하고, n은 노드의 개수다.

다음 트리를 보자.

루트는 노드 1이다. 1의 왼쪽 자식은 2, 오른쪽 자식은 3이다. 노드 4, 5, 6, 7은 자식이 없다. 높이는 다음과 같다.

• 노드 1: 0
• 노드 2와 3: 1
• 노드 4, 5, 6, 7: 2

다음 트리는 조금 다르다.

노드 1이 여전히 루트이고 왼쪽 자식은 2, 오른쪽 자식은 3이다. 다만 3에게는 오른쪽 자식만 있고, 노드 4에게는 왼쪽 자식 5만 있다. 높이는 다음과 같다.

• 노드 1: 0
• 노드 2와 3: 1
• 노드 4: 2
• 노드 5: 3

첫째 줄에 노드의 개수 n이 주어진다. ($1 \le n \le 20$)

다음 n개의 줄에는 각 노드의 부모가 한 줄에 하나씩 주어진다. 즉, 입력의 둘째 줄은 노드 1의 부모, 셋째 줄은 노드 2의 부모다. 루트는 -1로 표시한다. 노드 1이 항상 루트인 것은 아니다.

n개의 줄을 출력한다. 첫째 줄에는 노드 1의 높이, 둘째 줄에는 노드 2의 높이를 출력하고, 같은 방식으로 계속한다.