Anticommutative implication

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef is impressed by mathematical logic and linear algebra. He wants to combine his favorite subjects, so he introduced the concept of logical operations on boolean matrices.
He defines A → B to be a matrix C such that C_{ij} = A_{ij} → B_{ij} and ¬ A to be a matrix B such that B_{ij} = ¬ A_{ij}
Now Chef wants to study such system of equations: A → X = ¬ O and X → A = O
Where O is matrix such that all its entries is 0.
However, Chef realized that such system has solution if and only if A = O. Since such solution is too trivial, Chef has decided to search for an approximate solution for arbitrary A. Thus, Chef is searching for such X that A → X = ¬ O and X → A has as much as possible entries which are equal to 0.
But the solution space turned to be very large, so he reduced it to a matrices of a special form. Now he is looking for X such that X_{ij} = y_{i} xor y_{j} for some boolean vector y. Since now X is symmetric, Chef restricts A to also be symmetric.
Help Chef to resolve this difficult problem, or say that there is no solution.
Here → denotes the logical implication. p → q = !p  (p && q). Here ¬ denotes logical negation. ¬p = !p
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of A. The next N lines contain N spaceseparated integers A[i]_{1}, A[i]_{2}, ..., A[i]_{N} denoting the ith row of matrix A.
It's guaranteed that A is symmetric.
Output
For each test case, output a single line containing N integers  vector y, described in the statement, if there is a solution, or 1, if there is not. In case there are several solutions, print any solution.
Constraints and Subtasks
 0 ≤ A_{ij} ≤ 1
Subtask 1: (15 points)
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 10
Subtask 2: (25 points)
 1 ≤ T ≤ 500
 1 ≤ N ≤ 20
Subtask 3: (60 points)
 1 ≤ T ≤ 100
 1 ≤ N ≤ 1000
 The sum of N^{2} over all test cases in one test file does not exceed 10^{6}
Example
Input: 3 4 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 4 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 2 0 0 0 0 Output: 0 0 1 1 1 0 1
Explanation
Example case 1.
Matrix which is determined by vector y is
0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0
Then A → X = ¬ O and X → A is
1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1
Example case 2.
A_{11} = 1 and X_{11} = y_{1} xor y_{1} = 0. So A_{11} → X_{11} = 0 and condition A → X = ¬ O can not be satisfied.
Author:  kaizer 
Editorial  http://discuss.codechef.com/problems/ANCOIMP 
Tags  kaizer 
Date Added:  29032015 
Time Limit:  0.5  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 