시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 26 13 12 54.545%

문제

많은 프로그래밍 언어는 라이브러리 함수를 이용해서 배열의 값을 정렬할 수 있다. 이 함수를 사용해서 정렬을 하려면, less(x,y)와 같은 비교 함수를 작성해야 한다.

less(x,y)는 정렬한 순서에서 x가 y의 앞에 온다면 true를 리턴하는 함수이다. 이러한 함수는 항상 이치에 맞아야 한다. 즉, 서로 다른 두 원소 x와 y에 대해서, less(x,y)와 less(y,x)중 하나만 true가 되어야 한다.

이 문제에서는 수열에서 도치가 발생하지 않은 경우에 정렬되었다고 한다. less(x,y)에 대한 도치란, 크기가 n인 배열 A에서 less(A[j], A[i]) = true (0 ≤ i < j < n)를 만족하는 경우이다. (less(A[i], A[j]) = false와 동등한 의미가 아니다)

안타깝게도 어떤 프로그래머는 이런 비교 함수를 신중하게 작성하지 않는다. 이러한 경우에는 절대로 수열을 정렬할 수 없는 경우가 생길수도 있다.

less함수의 결과가 모두 주어진다. 이 때, 이 함수를 이용해서 정렬했을 때, 도치의 개수를 최소가 되는 순열을 구하는 프로그램을 작성하시오.

입력

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

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 주어진 비교 함수로 정렬했을 때, 도치의 개수가 최소가 되는 순열을 출력한다. 그 다음 줄에는 그 순열에서 도치의 개수를 출력한다. 만약, 도치의 개수가 같은 순열이 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다.

예제 입력

4
0111
0000
0100
0110
3
011
011
011
6
101010
011010
110110
000000
111010
001010
0

예제 출력

0 3 2 1
0
0 1 2
1
0 1 5 2 3 4
5

힌트