Finding the matrix

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a matrix B with size N × N. Each element of this matrix is an integer from the set {1, 0, 1}.
Determine if it's possible to express B as A · A^{T}, where A is a matrix of integers with size N × N. (Here, A^{T} is the transpose of A; see below for its definition.) If it is possible, find the lexicographically smallest A such that B = A · A^{T}.
The transpose of a matrix is created by flipping that matrix around its main diagonal — formally, the element at row i and column j of matrix A^{T} is the same as the element at row j and column i of matrix A, for each valid i, j. For more details, see Wikipedia.
For two matrices C and D with size N × N, we will say that C is lexicographically smaller than D if the sequence c = C_{1,1}, C_{1,2}, ..., C_{1,N}, C_{2,1}, C_{2,2}, ..., C_{2,N}, ..., C_{N,1}, ..., C_{N,N} is lexicographically smaller than d = D_{1,1}, D_{1,2}, ..., D_{1,N}, D_{2,1}, D_{2,2}, ..., D_{2,N}, ..., D_{N,1}, ..., D_{N,N}. That is, there must be a valid index i such that c_{i} and d_{i} differ, and the smallest such index must satisfy c_{i} < d_{i}.
Input
 The first line of the input contains a single 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.
 The next N lines describe matrix B. Each of these lines contains N spaceseparated integers. The jth integer on the ith line denotes B_{i,j}, the element at row i and column j of B.
Output
For each test case: If no valid matrix A exists, print a single line containing the integer 1.
 Otherwise, print N lines; each of them should contain N spaceseparated integers.
 The jth integer on the ith line should denote the element at row i and column j of matrix A.
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 1000
 1 ≤ B_{i,j} ≤ 1 for each valid i, j
 sum of N for all test cases ≤ 1000
Example
Input: 1 2 1 1 1 1 Output: 1 0 1 0
Explanation
Example case 1: You can check by brute force that this is the lexicographically smallest possible valid matrix A.
Author:  sidhant007 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/FINDA 
Tags  bipartite, constructive, cook90, maths, mediumhard, sidhant007 
Date Added:  16012018 
Time Limit:  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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, 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. 