Gilbert jest administratorem sieci w firmie Ginkgo. Jego szefa złości bałagan w kablach sieciowych na podłodze. W końcu podszedł do Gilbert i poprosił leniwego administratora o przedstawienie połączeń komputerów i przełączników. Ponieważ Gilbert jest programistą, bardzo niechętnie chodzi po biurze i ogląda kable oraz przełączniki. Postanowił więc wykonać zadanie za pomocą pomiarów i odrobiny matematycznego myślenia, cały czas siedząc przed komputerem. Twoim zadaniem jest pomóc mu, pisząc program odtwarzający topologię sieci z pomiarów.

Liczba komputerów jest znana, a liczba przełączników nieznana. Każdy komputer jest połączony kablem z jednym przełącznikiem i z niczym innym. W szczególności komputery nigdy nie łączą się bezpośrednio ze sobą, a jeden komputer nie łączy się z dwoma lub więcej przełącznikami. Przełączniki są połączone kablami i tworzą drzewo (spójny graf nieskierowany bez cykli). Żaden przełącznik nie jest bezużyteczny: każdy znajduje się na ścieżce między co najmniej jedną parą komputerów.

Łącznie komputery i przełączniki tworzą drzewo, którego liśćmi są komputery, a wierzchołkami wewnętrznymi przełączniki (patrz rysunek 9).

Gilbert mierzy odległości między wszystkimi parami komputerów. Odległość dwóch komputerów to po prostu liczba przełączników na ścieżce między nimi plus 1. Równoważnie, jest to liczba kabli służących do ich połączenia. Możesz się zastanawiać, jak Gilbert uzyskuje te odległości wyłącznie z pomiarów. Potrafi to dzięki bardzo zaawansowanej technice przetwarzania statystycznego, którą wynalazł. Prosimy nie pytać o szczegóły.

Dostajesz zatem macierz opisującą odległości między liśćmi drzewa. Twoim zadaniem jest odtworzyć z niej drzewo.

Wejście

Wejście to ciąg macierzy odległości, po którym następuje wiersz zawierający pojedyncze 0. Każda macierz ma następujący format.

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

Rysunek 9: Komputery i przełączniki

$N$ jest rozmiarem macierzy, czyli liczbą wierszy i kolumn. $a_{ij}$ podaje odległość między $i$-tym liściem (komputerem) a $j$-tym. Możesz założyć, że $2 \le N \le 50$, a macierz jest symetryczna i ma same zera na przekątnej. Zatem $a_{ii}=0$ i $a_{ij}=a_{ji}$ dla każdego $i,j$. Każdy element poza przekątną $a_{ij}$ ($i\ne j$) spełnia $2 \le a_{ij} \le 30$. Możesz założyć, że rozwiązanie zawsze istnieje, czyli istnieje drzewo o podanych odległościach między liśćmi.

Wyjście

Dla każdej macierzy znajdź drzewo o podanych odległościach między liśćmi. Następnie wypisz stopień każdego wierzchołka wewnętrznego (czyli liczbę kabli przylegających do każdego przełącznika), wszystkie w jednym wierszu i w kolejności rosnącej. Liczby w wierszu należy rozdzielać pojedynczą spacją. Wiersz nie może zawierać żadnych innych znaków, w tym końcowych spacji.

Przykład

Wejście 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

Wyjście 1

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