Network Mess

길버트는 은행나무 회사의 네트워크 관리자다. 그의 상사는 바닥에 어지럽게 널린 네트워크 케이블에 화가 나서, 결국 이 게으른 관리자에게 컴퓨터와 스위치가 어떻게 연결되어 있는지 그림으로 그려 보라고 지시했다. 프로그래머인 길버트는 사무실을 돌아다니며 눈으로 케이블과 스위치를 확인하는 일을 몹시 꺼린다. 대신 그는 컴퓨터 앞에 앉은 채로 측정과 약간의 수학적 추론만으로 이 일을 끝내기로 했다. 여러분의 임무는 측정값으로부터 네트워크 구조를 복원하는 프로그램을 작성해 그를 돕는 것이다.

컴퓨터의 개수는 알려져 있지만 스위치의 개수는 알 수 없다. 각 컴퓨터는 케이블로 스위치 하나에만 연결되며 그 밖에는 아무것에도 연결되지 않는다. 즉, 컴퓨터가 다른 컴퓨터와 직접 연결되거나 둘 이상의 스위치에 연결되는 일은 결코 없다. 스위치들은 케이블로 서로 연결되어 트리(사이클이 없는 연결 무방향 그래프)를 이룬다. ‘쓸모없는’ 스위치는 없다. 다시 말해, 모든 스위치는 적어도 한 쌍의 컴퓨터 사이의 경로 위에 놓여 있다.

결국 컴퓨터와 스위치가 함께 하나의 트리를 이루며, 이 트리의 잎(leaf)은 컴퓨터이고 내부 노드는 스위치다.

길버트는 모든 컴퓨터 쌍 사이의 거리를 측정한다. 두 컴퓨터 사이의 거리는 두 컴퓨터를 잇는 경로 위에 있는 스위치의 수에 1을 더한 값이며, 이는 두 컴퓨터를 연결하는 데 쓰인 케이블의 수와 같다. 길버트가 오직 측정만으로 이 거리들을 어떻게 얻는지 궁금하겠지만, 그는 자신이 고안한 매우 정교한 통계 처리 기법으로 그렇게 한다. 자세한 내용은 묻지 말자.

따라서 트리의 잎들 사이의 거리를 나타내는 행렬이 주어진다. 여러분의 임무는 이 행렬로부터 트리를 복원하는 것이다.

입력은 여러 개의 거리 행렬로 이루어지며, 마지막에는 0 하나만 있는 줄이 온다. 각 거리 행렬의 형식은 다음과 같다.

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

$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$을 만족한다. 항상 해가 존재한다고 가정해도 좋다. 즉, 주어진 잎 사이의 거리를 갖는 트리가 반드시 존재한다.

각 거리 행렬에 대해, 주어진 잎 사이의 거리를 갖는 트리를 찾아라. 그런 다음 각 내부 노드의 차수(즉, 각 스위치에 연결된 케이블의 수)를 오름차순으로 한 줄에 모두 출력한다. 한 줄의 수들은 공백 하나로 구분한다. 줄에는 끝의 공백을 포함해 그 밖의 어떤 문자도 있어서는 안 된다.