대충 정렬

많은 프로그래밍 언어는 라이브러리 함수로 배열을 정렬할 수 있다. 이런 함수를 쓰려면 두 원소의 순서를 정하는 비교 함수 less(x, y)를 함께 넘겨야 한다. less(x, y)는 정렬된 순서에서 x가 y보다 앞에 와야 하면 true를, 그렇지 않으면 false를 반환한다.

원래 이런 비교 함수는 항상 일관되어야 한다. 즉, 서로 다른 두 원소 x, y에 대해 less(x, y)와 less(y, x) 중 정확히 하나만 true여야 한다.

이 문제에서는 배열에 도치(inversion) 가 하나도 없을 때 그 배열이 정렬되었다고 한다. 크기가 n인 배열 A에서 도치란, $0 \le i < j < n$이면서 less(A[j], A[i]) = true인 위치의 쌍 $(i, j)$를 말한다. (이는 less(A[i], A[j]) = false인 것과 같은 뜻이 아니다.)

안타깝게도 어떤 프로그래머는 비교 함수를 엉성하게 작성한다. 이런 함수로는 원소를 어떻게 배치해도 도치가 남는, 즉 배열을 결코 완전히 정렬할 수 없는 경우가 생길 수도 있다.

less 함수의 모든 반환값이 주어진다. 이 비교 함수 기준으로 도치의 개수가 가장 적어지는, 0번부터 n-1번까지의 원소를 한 번씩 배치한 순열을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 배열의 크기 n이 주어진다 ($1 \le n \le 18$). 원소에는 0번부터 n-1번까지 번호가 매겨져 있다. 이어지는 n개의 줄에는 길이가 n인 이진 문자열이 주어지며, i번째 줄(0번부터 셈)의 j번째 문자는 less(i, j)의 반환값이다. 0은 false, 1은 true를 뜻한다.

입력의 마지막 줄에는 0이 하나 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다, 주어진 비교 함수로 정렬했을 때 도치의 개수가 최소가 되는 순열을 공백 하나로 구분하여 한 줄에 출력한다. 그다음 줄에는 그 순열에서의 도치 개수를 출력한다.

도치의 개수가 최소인 순열이 여러 개라면, 사전 순으로 가장 앞서는 것을 출력한다.