Network Mess

Gilbert is the network administrator of the Ginkgo company. His boss is furious about the messy network cables strewn across the floor and has finally ordered the lazy administrator to draw a diagram of how the computers and switches are connected. Being a programmer, Gilbert is very reluctant to walk around the office and inspect the cables and switches with his own eyes. Instead he decides to finish the job while sitting at his computer, using only measurements and a little mathematical reasoning. Your job is to help him by writing a program that reconstructs the network topology from the measurements.

The number of computers is known, but the number of switches is not. Each computer is connected by a cable to exactly one switch and to nothing else. In particular, a computer is never connected directly to another computer, and never to two or more switches. The switches are connected by cables so that they form a tree (a connected undirected graph with no cycles). No switch is “useless”: every switch lies on the path between at least one pair of computers.

Altogether the computers and switches form a single tree whose leaves are the computers and whose internal nodes are the switches (see the figure).

Gilbert measures the distance between every pair of computers. The distance between two computers is the number of switches on the path between them plus one, which is exactly the number of cables used to connect them. You may wonder how Gilbert obtains these distances from measurement alone; he does so with a very sophisticated statistical technique of his own invention. Please do not ask for the details.

You are therefore given a matrix of the distances between the leaves of a tree. Your job is to reconstruct the tree from it.

The input is a series of distance matrices, followed by a line containing a single 0. Each distance matrix has the following format.

N
a11 a12 ... a1N
a21 a22 ... a2N
...
aN1 aN2 ... aNN

$N$ is the size of the matrix, that is, the number of rows and the number of columns. $a_{ij}$ is the distance between the $i$-th leaf (computer) and the $j$-th leaf. You may assume $2 \le N \le 50$, and the matrix is symmetric with all diagonal elements equal to zero; that is, $a_{ii} = 0$ and $a_{ij} = a_{ji}$ for every $i$ and $j$. Each off-diagonal element $a_{ij}$ ($i \ne j$) satisfies $2 \le a_{ij} \le 30$. You may assume a solution always exists; that is, there is always a tree that realizes the given distances between the leaf nodes.

For each distance matrix, find a tree that realizes the given distances between the leaf nodes. Then output the degree of each internal node (that is, the number of cables adjoining each switch), all on a single line and in ascending order. The numbers on a line must be separated by a single space. A line must not contain any other characters, including trailing spaces.