Gilbert は Ginkgo 社のネットワーク管理者である。彼の上司は床の乱雑なネットワークケーブルに腹を立てている。ついに上司は Gilbert のところへ来て、この怠惰な管理者にコンピュータとスイッチの接続を図示するよう求めた。プログラマである彼は、オフィス中を歩き回ってケーブルやスイッチを目で確かめることを非常に嫌がる。代わりに、ずっとコンピュータの前に座ったまま、測定と少しの数学的思考で仕事を済ませることにした。あなたの任務は、測定値からネットワークの構造を再構築するプログラムを書いて彼を助けることである。

コンピュータの台数は既知で、スイッチの数は未知である。各コンピュータはケーブルを介して一つのスイッチだけに接続し、他のものには接続しない。具体的には、コンピュータ同士は直接接続されず、一台が二つ以上のスイッチに接続されることもない。スイッチはケーブルで接続され、木（閉路を持たない連結な無向グラフ）をなす。無用なスイッチはない。つまり、各スイッチは少なくとも一組のコンピュータ間の経路上にある。

全体として、コンピュータとスイッチは、コンピュータが葉、スイッチが内部頂点である木をなす（図 9 参照）。

Gilbert はすべてのコンピュータの組について距離を測る。二台間の距離は、その間の経路にあるスイッチの数に 1 を足したものである。同じことだが、それらの接続に使われるケーブルの数でもある。Gilbert が測定だけでどう距離を得るのか不思議に思うかもしれない。彼は自ら発明した非常に高度な統計処理技術でそれを行う。詳細は聞かないでほしい。

したがって、木の葉の間の距離を記述する行列が与えられる。あなたの任務は、それから木を構築することである。

入力

入力は距離行列の列で、その後に 0 一つだけを含む行が続く。各距離行列の形式は次のとおりである。

$$N$$

$$\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1N}\\a_{21}&a_{22}&\cdots&a_{2N}\\\vdots&\vdots&\ddots&\vdots\\a_{N1}&a_{N2}&\cdots&a_{NN}\end{pmatrix}$$

図 9: コンピュータとスイッチ

$N$ は行列のサイズ、すなわち行数と列数である。$a_{ij}$ は $i$ 番目の葉頂点（コンピュータ）と $j$ 番目との距離を表す。$2 \le N \le 50$ であり、行列は対称で対角成分はすべて 0 と仮定してよい。すなわち、各 $i,j$ について $a_{ii}=0$、$a_{ij}=a_{ji}$ である。各非対角成分 $a_{ij}$（$i\ne j$）は $2 \le a_{ij} \le 30$ を満たす。常に解があると仮定してよい。つまり、与えられた葉間距離を持つ木が存在する。

出力

各距離行列について、与えられた葉間距離を持つ木を求めよ。そして各内部頂点の次数（すなわち各スイッチに接続するケーブルの数）を、すべて昇順で一行に出力せよ。行内の数は一つの空白で区切る。行には、末尾の空白を含めて他の文字を含めてはならない。

入出力例

入力 1

4
    0   2   2   2
    2   0   2   2
    2   2   0   2
    2   2   2   0
4
    0   2   4   4
    2   0   4   4
    4   4   0   2
    4   4   2   0
2
     0 12
    12 0
0

出力 1

4
2 3 3
2 2 2 2 2 2 2 2 2 2 2