이진 연립방정식

크기가 $N\times M$인 행렬 $A$와 길이가 $N$인 벡터 $b$가 주어진다. $A$와 $b$의 모든 원소는 $0$ 또는 $1$이다. $A$의 행 번호와 $b$의 원소 번호는 $0$부터 $N-1$까지, $A$의 열 번호는 $0$부터 $M-1$까지이다.

길이가 $M$이고 모든 원소가 $0$ 또는 $1$인 벡터 $x$에 대해 연립방정식 $Ax=b$를 풀어 보자. 모든 연산은 $2$로 나눈 나머지로 계산한다.

왼쪽 열부터 피벗을 선택하여 계수 행렬을 기약 행 사다리꼴로 만들고, 자유변수를 모두 $0$으로 둔 해를 구한다. 계수 행렬의 랭크와 각 열의 피벗 행 번호도 구해야 한다. 해가 존재하지 않을 수도 있다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le1\,000)$

각 테스트 케이스의 첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(0\le N,M\le2\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 행 번호 순서대로 0과 1로 이루어진 길이가 $M+1$인 문자열이 주어진다. 각 문자열의 앞 $M$개 문자는 해당 행의 계수이고, 마지막 문자는 $b$의 대응하는 원소이다.

모든 테스트 케이스에 대한 $N(M+1)$의 합은 $4\cdot10^6$ 이하이다.

각 테스트 케이스에 대해 세 줄에 걸쳐 출력한다.

첫 번째 줄에 계수 행렬 $A$의 랭크를 출력한다.

두 번째 줄에 각 열의 피벗 행 번호를 열 번호 순서대로 공백으로 구분하여 출력한다. 자유열은 $-1$을 출력한다. $M=0$이면 이 줄은 빈 줄이다.

세 번째 줄에 본문의 규칙에 따른 해를 열 번호 순서대로 길이가 $M$인 이진 문자열로 출력한다. 해가 없으면 NONE을, 변수가 없고 해가 있으면 EMPTY를 출력한다.