Help the problem setter

Preparing a problem for a programming contest takes a lot of time. You must write the statement and a reference solution, and you also have to craft difficult input files. In this problem you help the problem setter build the input for one specific task.

That task is about finding the optimal binary search tree given the probabilities with which its nodes are accessed. Here you solve the reverse problem: you are given the tree that should be optimal, and you must find access probabilities for which this tree is the unique optimal binary search tree. Every definition you need is given below.

A binary search tree is defined inductively:

• The empty tree, with no nodes at all, is a binary search tree.
• Every non-empty binary search tree has a root, a node labelled with an integer, together with two binary search trees that are the left and right subtrees of the root.
• The left subtree contains no node whose label is $\ge$ the label of the root.
• The right subtree contains no node whose label is $\le$ the label of the root.

To locate a node, the following search procedure is used. Start at the root. Compare the label of the current node with the desired label. If they are equal, the node has been found. Otherwise, if the desired label is smaller, continue the search in the left subtree; if it is larger, continue in the right subtree.

The access cost of a node is the number of nodes visited until it is found, so the root has cost $1$, each child of the root has cost $2$, and so on. The expected access cost of a tree is $\sum_{i=1}^{n} p_i \cdot c_i$, where $p_i$ is the access probability of the node with label $i$ and $c_i$ is its access cost. An optimal binary search tree is one whose expected access cost is minimum.

The input contains several test cases. Each test case begins with an integer $n$ ($1 \le n \le 50$), the number of nodes in the optimal binary search tree. The labels of the nodes are the integers from $1$ to $n$. The next $n$ lines describe the structure of the tree: the $i$-th line contains two integers, the labels of the roots of the left and right subtrees of the node labelled $i$, using $-1$ for an empty subtree. The input always describes a valid binary search tree. The last test case is followed by a line containing a single $0$, which must not be processed.

For each test case print one line with $n$ integers: the access frequency of every node, in increasing order of labels. The access probability of a node equals its frequency divided by the sum of all frequencies, and the frequencies must make the given tree the unique optimal binary search tree.

Many frequency assignments satisfy this requirement, so to keep the answer unique this problem fixes one canonical assignment that is always valid. Compute it from the bottom up: the frequency of every node is $1$ plus the total frequency of all nodes contained in its subtrees. Equivalently, every leaf has frequency $1$, and every internal node has frequency equal to $1$ plus the sum of the frequencies of all of its proper descendants. Print these frequencies in increasing order of labels.

With this rule every frequency is a positive integer that fits in a signed 64-bit integer: for $n \le 50$ no value exceeds $2^{49}$, which is far below $2^{63} - 1$.

For example, a binary search tree whose root is the node labelled $2$, with the nodes labelled $1$ and $3$ as its left and right children, looks like this:

  2
 / \
1   3