Gilbert es el administrador de la red de la empresa Ginkgo. Su jefe está enfadado por el desorden de cables de red en el suelo. Finalmente, se acercó a Gilbert y le pidió al perezoso administrador que ilustrara cómo se conectan las computadoras y los conmutadores. Como es programador, se resiste a recorrer la oficina y examinar los cables y conmutadores con sus propios ojos. En cambio, decidió hacer el trabajo mediante mediciones y un poco de razonamiento matemático, sentado siempre frente a su computadora. Tu tarea es ayudarle escribiendo un programa que reconstruya la topología de la red a partir de las mediciones.

Hay un número conocido de computadoras y uno desconocido de conmutadores. Cada computadora se conecta mediante un cable a uno de los conmutadores y a nada más. En concreto, una computadora nunca se conecta directamente a otra ni a dos o más conmutadores. Los conmutadores se conectan mediante cables formando un árbol (un grafo no dirigido conexo y sin ciclos). Ningún conmutador es inútil: cada uno está en el camino entre al menos una pareja de computadoras.

En conjunto, las computadoras y conmutadores forman un árbol cuyas hojas son computadoras y cuyos nodos internos son conmutadores (véase la figura 9).

Gilbert mide las distancias entre todas las parejas de computadoras. La distancia entre dos es simplemente el número de conmutadores en el camino entre ellas más 1. Equivalentemente, es el número de cables usados para conectarlas. Puede que te preguntes cómo obtiene Gilbert estas distancias solo mediante mediciones. Puede hacerlo con una técnica muy sofisticada de procesamiento estadístico que inventó. Por favor, no preguntes los detalles.

Por tanto, recibes una matriz que describe las distancias entre hojas de un árbol. Tu tarea es construir el árbol a partir de ella.

Entrada

La entrada es una serie de matrices de distancias, seguida de una línea que contiene un único 0. Cada matriz tiene el siguiente formato.

$$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}$$

Figura 9: Computadoras y conmutadores

$N$ es el tamaño de la matriz, es decir, su número de filas y columnas. $a_{ij}$ da la distancia entre la hoja $i$ (computadora) y la hoja $j$. Puedes suponer que $2 \le N \le 50$ y que la matriz es simétrica con todos los elementos diagonales iguales a cero. Es decir, $a_{ii}=0$ y $a_{ij}=a_{ji}$ para cada $i,j$. Cada elemento no diagonal $a_{ij}$ ($i\ne j$) satisface $2 \le a_{ij} \le 30$. Puedes suponer que siempre existe una solución: hay un árbol con las distancias dadas entre sus hojas.

Salida

Para cada matriz, encuentra un árbol con las distancias dadas entre hojas. Después imprime el grado de cada nodo interno (el número de cables adyacentes a cada conmutador), todos en una sola línea y en orden ascendente. Los números deben separarse por un único espacio. La línea no debe contener otros caracteres, incluidos espacios finales.

Ejemplos

Entrada 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

Salida 1

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