Optimisation

A company decides to simulate on computer the process of manufacturing its own goods. In order to do that, it makes the following observations:

The whole process can be splitted into several steps; between them there are some dependencies. This can be represented by a diagram (graph), which we suppose to be only one for all goods produced by company as in figure 1;
First step designates the start of manufacturing process;there is only one first step, denoted by the number 1;
There are not steps isolated or outside the process (every step is linked by a path with the first step);
Some steps are total dependants; so, we claim that the step i is total dependant of step j if every path in the fabrication process cannot arrive to i without was passing through j. So, all steps are total dependants of step 1. Example: In the process shown by the figure 1 the step 4 is total dependant of step 3, steps 5,6 and 7 are total dependants of 4 (hence of 3), but step 3 is not total dependant of step 2. The Computing Center Dept. of company notes that whole manufacturing process is easier to be controlled if it would be structured by a tree, as follows:

2/3 • All steps of manufacturing process are nodes of the tree; • Each node ensures total dependence of all its own descendants; The tree associated to the diagram from figure 1 is shown in figure 2. Your task is to write a program that builds this dependence tree. Input The input file contains several input data sets. An input data set has the following format: n - number of steps of manufacturing process (2 ≤ n ≤ 99); a11 a12 ... a1n a21 a22 ... a2n . . ... . an1 an2 ... ann where aij = 1 if step j follows directly step i in the process diagram, otherwise aij = 0. Output At output, the program must write n − 1 lines for every input data set; each line has the format: ij with the meaning that node j is a direct descendant of node i in the tree. The pair (i1j1) follows (i2j2) ifandonlyif(i1 <i2)or(i1 =i2 andj1 <j2).

3/3 Sample Input 10 0110000000 0010000000 0001000000 0010110000 0000001000 0000001000 0001000100 0010000011 1000000000 0000001000 Sample Output 12 13 34 45 46 47 78 89 8 10