루트로 회전시키기

루트로 회전(rotate-to-root)은 이진 탐색 트리의 균형을 맞추기 위한 휴리스틱이다. 이 문제에서 노드에 저장된 값은 중요하지 않으며, 휴리스틱이 트리의 모양을 어떻게 바꾸는지에만 관심을 둔다.

이진 트리는 비어 있거나, 왼쪽 자식과 오른쪽 자식을 가지는 하나의 노드로 이루어지며 각 자식도 다시 이진 트리이다. 어떤 노드도 부모를 둘 이상 가지지 않고 사이클이 없으므로, 비어 있지 않은 트리에는 부모가 없는 노드가 정확히 하나 있으며 이를 루트라고 한다.

이 휴리스틱은 어떤 노드 $X$가 접근될 때 작동한다. $X$가 루트가 아닌 동안 다음 과정을 반복한다.

• $X$가 부모 $P$의 왼쪽 자식이면 오른쪽 회전을 수행한다. $X$의 오른쪽 자식을 $B$라 하자. $X$가 $P$의 자리를 대신하고(따라서 $P$에게 원래 부모가 있었다면 그 부모가 $X$의 부모가 된다), $P$는 $X$의 오른쪽 자식이 되며, $B$는 $P$의 왼쪽 자식이 된다. $X$의 왼쪽 자식과 $P$의 오른쪽 자식은 바뀌지 않는다.
• $X$가 부모 $P$의 오른쪽 자식이면 왼쪽 회전을 수행한다. $X$의 왼쪽 자식을 $B$라 하자. $X$가 $P$의 자리를 대신하고, $P$는 $X$의 왼쪽 자식이 되며, $B$는 $P$의 오른쪽 자식이 된다. $X$의 오른쪽 자식과 $P$의 왼쪽 자식은 바뀌지 않는다.

각 회전은 노드들의 중위 순서를 유지하면서 $X$를 루트 쪽으로 한 단계 올린다. 충분히 반복하면 $X$가 루트가 된다.

이진 트리의 높이는 루트에서 잎까지의 경로 중 가장 긴 경로에 있는 노드의 개수이다. 형식적으로, 빈 트리의 높이는 $0$이고, 루트의 두 부분트리가 $A$, $B$인 비어 있지 않은 트리의 높이는 $1 + \max(\mathrm{height}(A), \mathrm{height}(B))$이다.

이진 트리가 주어질 때, 각 노드 $X$에 대해 $X$를 루트로 회전시킨 뒤 트리의 높이가 얼마가 되는지 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 노드의 개수 $N$이 주어지며, $1 \le N \le 10^5$이다.

이어지는 $N$개의 줄에는 각각 두 정수가 주어진다. $i$번째 줄은 노드 $i$의 왼쪽 자식 $l_i$와 오른쪽 자식 $r_i$이다. 값이 $0$이면 해당 자식은 빈 트리이고, 그렇지 않으면 $1 \le l_i, r_i \le N$이다. 입력은 항상 올바른 이진 트리를 나타낸다.

마지막 테스트 케이스 다음에는 정수 $0$ 하나만 있는 줄이 주어진다. 이 줄은 입력의 끝을 나타내며 처리하지 않는다.

각 테스트 케이스마다 $N$개의 줄을 출력한다. $i$번째 줄에는 노드 $i$를 루트로 회전시킨 뒤 트리의 높이를 출력한다.