Rotate to Root

Rotate-to-root is a heuristic for balancing binary search trees. The values stored in the tree are irrelevant here; we only care about how the heuristic changes the tree's shape.

A binary tree is either empty or a node with a left child and a right child, each of which is itself a binary tree. No node has more than one parent and there are no cycles, so a non-empty tree has exactly one node with no parent, called the root.

The heuristic is triggered when some node $X$ is accessed. While $X$ is not the root, the following step is repeated:

• If $X$ is the left child of its parent $P$, perform a right rotation. Let $B$ be $X$'s right child. Then $X$ takes $P$'s place (so $P$'s former parent, if any, becomes $X$'s parent), $P$ becomes $X$'s right child, and $B$ becomes $P$'s left child. $X$'s left child and $P$'s right child are unchanged.
• If $X$ is the right child of its parent $P$, perform a left rotation. Let $B$ be $X$'s left child. Then $X$ takes $P$'s place, $P$ becomes $X$'s left child, and $B$ becomes $P$'s right child. $X$'s right child and $P$'s left child are unchanged.

Each rotation moves $X$ one level closer to the root while preserving the in-order sequence of the nodes; after enough rotations $X$ becomes the root.

The height of a binary tree is the number of nodes on the longest path from the root to a leaf. Formally, the empty tree has height $0$, and a non-empty tree whose root has subtrees $A$ and $B$ has height $1 + \max(\mathrm{height}(A), \mathrm{height}(B))$.

Given a binary tree, determine, for every node $X$, the height the tree would have after $X$ is rotated to the root.

The input contains several test cases. The first line of a test case is an integer $N$, the number of nodes, with $1 \le N \le 10^5$.

Each of the next $N$ lines contains two integers; line $i$ gives $l_i$ and $r_i$, the left and right children of node $i$. A value of $0$ means that child is the empty tree; otherwise $1 \le l_i, r_i \le N$. The input is guaranteed to describe a valid binary tree.

A line containing a single $0$ follows the last test case; it is a terminator and must not be processed.

For each test case output $N$ lines; line $i$ is the height of the tree after node $i$ is rotated to the root.