Sloppy Sort

Many programming languages can sort an array with a library function. To use such a function you must supply a comparison function less(x, y) that decides the order of two elements: less(x, y) returns true if x must come before y in the sorted order, and false otherwise.

Normally such a comparison function has to be consistent: for any two distinct elements x and y, exactly one of less(x, y) and less(y, x) is true.

In this problem we say an array is sorted when it contains no inversion. For an array A of size n, an inversion is a pair of positions $(i, j)$ with $0 \le i < j < n$ such that less(A[j], A[i]) = true. (This is not the same as less(A[i], A[j]) = false.)

Unfortunately, some programmers write this comparison function carelessly. With such a function there may be no arrangement of the array that removes every inversion — that is, the array can never be fully sorted.

You are given every return value of the less function. Find an arrangement of the elements 0 through n-1 (each used exactly once) that has the fewest inversions under this comparison function.

The input consists of several test cases.

The first line of each test case contains the array size n ($1 \le n \le 18$). The elements are numbered from 0 to n-1. Each of the next n lines contains a binary string of length n; the j-th character of the i-th line (both 0-indexed) is the return value of less(i, j), where 0 means false and 1 means true.

The last line of the input contains a single 0, which marks the end of the input.

For each test case, print on one line the permutation that minimizes the number of inversions under the given comparison function, with the elements separated by single spaces. On the next line, print the number of inversions of that permutation.

If several permutations achieve the same minimum number of inversions, print the lexicographically smallest one.