Problem:


Problem G: Network Mess

Gilbert is the network admin of Ginkgo company. His boss is mad about the messy network
cables on the floor. He finally walked up to Gilbert and asked the lazy network admin to illustrate
how computers and switches are connected. Since he is a programmer, he is very reluctant to
move throughout the office and examine cables and switches with his eyes. He instead opted
to get this job done by measurement and a little bit of mathematical thinking, sitting down in
front of his computer all the time. Your job is to help him by writing a program to reconstruct
the network topology from measurements.

There are a known number of computers and an unknown number of switches. Each computer
is connected to one of the switches via a cable and to nothing else. Specifically, a computer
is never connected to another computer directly, or never connected to two or more switches.
Switches are connected via cables to form a tree (a connected undirected graph with no cycles).
No switches are ‘useless.’ In other words, each switch is on the path between at least one pair
of computers.

All in all, computers and switches together form a tree whose leaves are computers and whose
internal nodes switches (See Figure 9).

Gilbert measures the distances between all pairs of computers. The distance between two com-
puters is simply the number of switches on the path between the two, plus one. Or equivalently,
it is the number of cables used to connect them. You may wonder how Gilbert can actually
obtain these distances solely based on measurement. Well, he can do so by a very sophisticated
statistical processing technique he invented. Please do not ask the details.

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

Input

The input is a series of distance matrices, followed by a line consisting of a single '0'. Each
distance matrix is formatted as follows.

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

N is the size, i.e. the number of rows and the number of columns, of the matrix. aij gives the
distance between the i-th leaf node (computer) and the j-th. You may assume 2 ≤ N ≤ 50 and
the matrix is symmetric whose diagonal elements are all zeros. That is, aii = 0 and aij = aji
for each i and j. Each non-diagonal element aij (i &ne; j) satisfies 2 ≤ aij ≤ 30. You may assume
there is always a solution. That is, there is a tree having the given distances between leaf nodes.

Output

For each distance matrix, find a tree having the given distances between leaf nodes. Then output
the degree of each internal node (i.e. the number of cables adjoining each switch), all in a single
line and in ascending order. Numbers in a line should be separated by a single space. A line
should not contain any other characters, including trailing spaces.

Sample Input

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

Output for the Sample Input

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



Sample input:
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


Sample output:
4
2 3 3
2 2 2 2 2 2 2 2 2 2 2

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    # function to update distance between switch and computer
    def dfs(sw_id, prev, dist):
        switch[sw_id].append(dist)
        for next_sw in adj[sw_id]:
            if next_sw != prev:
                dfs(next_sw, sw_id, dist + 1)
    
    while True:
        N = int(f_i.readline())
        if N == 0:
            break
        
        # distance table of computers
        dist_tbl = [list(map(int, f_i.readline().split())) for i in range(N)]
        
        switch = [[1]] # switch[sw][com]: distance between sw and com
        degree = [1]
        adj = [[]] # adjacency list of switches
        
        for dt_i in dist_tbl[1:]:
            # try to connect a computer to an existing switch
            for m, sw_m in enumerate(switch):
                for dist_j, dt_ij in zip(sw_m, dt_i):
                    if dist_j != dt_ij - 1:
                        break
                else: # found a switch to connect a computer
                    degree[m] += 1
                    dfs(m, m, 1)
                    break
                continue
            else: # no switch to connect
                # find an existing switch to connect additional switch to
                for m, sw_m in enumerate(switch):
                    g = (x - y for x, y in zip(dt_i, sw_m))
                    diff = next(g)
                    for d in g:
                        if d != diff:
                            break
                    else:
                        break
                
                # first additional switch
                sw = len(switch)
                switch.append([dist + 1 for dist in switch[m]])
                adj[m].append(sw)
                adj.append([m])
                degree[m] += 1
                degree.append(1)
                
                # second and subsequent additional switches
                for i in range(2, diff):
                    switch.append([dist + i for dist in switch[m]])
                    adj[sw].append(sw + 1)
                    adj.append([sw])
                    degree[sw] += 1
                    degree.append(1)
                    sw += 1
                
                # connect a computer to the last added switch
                degree[sw] += 1
                dfs(sw, sw, 1)
                
        degree.sort()
        print(' '.join(map(str, degree)))

solve()