#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <string>
#include <fstream>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include "supertrees.h"
using namespace std;
#define ll int
#define llu unsigned long long
#define ld long double
#define F first
#define S second
#define endl "\n"
#define MID ((l+r)/2)
#define sorv(a) sort(a.begin(),a.end())
#define revv(a) reverse(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define ins insert
#define pb push_back
#define inf 1e9
#define INF 1e18
#define MOD 1000000007
#define MOD2 998244353
typedef pair <ll, ll> ii;
typedef pair <ll,ii> iii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <iii> viii;
typedef set <ll> si;
typedef map <ll,ll> mi;
#ifndef ONLINE_JUDGE
//#define ONLINE_JUDGE
#endif
#ifndef ONLINE_JUDGE
template<typename T>void printArr(T *arr,ll l,ll m=0){if(m==1){for(ll i=0;i<l;i++)cout<<arr[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<l;i++)cout<<i<<": "<<arr[i]<<endl;}}
#define printArr2D(arr,n,m)cout<<endl;for(ll i=0;i<n;i++){for(ll j=0;j<m;j++)cout<<arr[i][j]<<" ";cout<<endl;}cout<<endl;
template<typename T>void printVct(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0; i<sz(v);i++)cout<<i<<": "<<v[i]<<endl;}}
template<typename T>void printVct2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j]<<" ";cout<<endl;}}
template<typename T>void printVctPair(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i].F<<":"<<v[i].S<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": "<<v[i].F<<" : "<<v[i].S<<endl;}}
template<typename T>void printVctPair2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j].F<<":"<<v[i][j].S<<" ";cout<<endl;}}
template<typename T>void printVctPair3(vector<T> v,ll m=0){cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": ("<<v[i].F<<" : "<<v[i].S.F<<" : "<<v[i].S.S<<")"<<endl;}
template<typename T1,typename T2>void printMap(map<T1,T2>mp){cout<<endl;for(typename map<T1,T2>::iterator it=mp.begin();it!=mp.end();it++)cout<<it->F<<" -> "<<it->S<<endl;}
template<typename T>void printSet(set<T>st,ll m=0){typename set<T>::iterator it;if(m){for(it=st.begin();it!=st.end();it++)cout<<*it<<" ";cout<<endl;}else{cout<<endl;for(it=st.begin();it!=st.end();it++)cout<<*it<<endl;}}
void check(ll n){cout<<"CHECKPOINT "<<n<<"\n\n";}
#define dbg(x) cout<<#x<<":"<<x<<endl
#define dbg2(x,y) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define dbg3(x,y,z) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define dbg4(x,y,z,w) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<endl
#define dbg5(x,y,z,w,v) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<endl
#define dbg6(x,y,z,w,v,u) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<" "<<#u<<":"<<u<<endl
#define dbgp(x) cout<<#x<<":("<<x.F<<" "<<x.S<<")"<<endl
#define dbgp2(x,y) cout<<#x<<":("<<x.F<<","<<x.S<<") "<<#y<<":("<<y.F<<","<<y.S<<")"<<endl
#define dbgt(x) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<")"<<endl
#define dbgt2(x,y) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<") "<<#y<<":("<<y.F<<" "<<y.S.F<<" "<<y.S.S<<")"<<endl
#else
template<typename T>void printArr(T *arr,ll l,ll m=0){}
#define printArr2D(arr,n,m)
template<typename T>void printVct(vector<T> v,ll m=0){}
template<typename T>void printVct2D(vector<vector<T> >v){}
template<typename T>void printVctPair(vector<T> v,ll m=0){}
template<typename T>void printVctPair2D(vector<vector<T> >v){}
template<typename T>void printVctPair3(vector<T> v,ll m=0){}
template<typename T1,typename T2>void printMap(map<T1,T2>mp){}
template<typename T>void printSet(set<T>st,ll m=0){}
void check(ll n){}
#define dbg(x)
#define dbg2(x,y)
#define dbg3(x,y,z)
#define dbg4(x,y,z,w)
#define dbg5(x,y,z,w,v)
#define dbg6(x,y,z,w,v,u)
#define dbgp(x)
#define dbgp2(x,y)
#define dbgt(x)
#define dbgt2(x,y)
#endif
const ll dx[8]={1,-1,0,0,1,1,-1,-1}, dy[8]={0,0,1,-1,1,-1,1,-1};
ll charToIntNum(char c){return (ll)c-48;}
char intToCharNum(ll n){return (char)n+48;}
ll charToIntLower(char c){return (ll)c-97;}
char intToCharLower(ll n){return (char)n+97;}
ll charToIntUpper(char c){return (ll)c-65;}
char intToCharUpper(ll n){return (char)n+65;}
void tabb(ll n){for(ll i=0;i<n;i++)cout<<"\t";}
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
void yesno(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
/*
2
1 0
0 1
2
1 3
3 1
2
1 2
2 1
3
1 1 1
1 1 1
1 1 1
3
1 2 2
2 1 2
2 2 1
4
1 2 2 2
2 1 2 2
2 2 1 1
2 2 1 1
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
7
1 2 2 2 2 1 1
2 1 2 2 2 2 2
2 2 1 2 1 2 2
2 2 2 1 2 2 2
2 2 1 2 1 2 2
1 2 2 2 2 1 1
1 2 2 2 2 1 1
//STEP 1 TESTS:
4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
5
1 1 0 0 1
1 1 0 0 0
0 0 1 1 1
0 0 1 1 0
1 0 1 0 1
5
1 1 0 0 1
1 1 0 0 1
0 0 1 1 0
0 0 1 1 0
1 1 0 0 1
//---------------
*/
bool step0(ll n, vector <vi> &p){
for(ll i =0; i<n; i++){
for (ll j=0; j<n; j++){
if (i == j && p[i][j] != 1) return false;
if (p[i][j] != p[j][i]) return false;
if (p[i][j] > 2) return false;
}
}
return true;
}
bool step1(ll n, vector <vi> &p, vi &mp, vector <vi> &g){
g.reserve(1000);
//build & check ones
for (ll i=0; i<n; i++){
if (mp[i] == -1){
g.pb(vi());
mp[i] = sz(g)-1;
g.back().pb(i);
}
for (ll j =0; j<n; j++){
if (i == j) continue;
if (p[i][j] > 0 && mp[j] != mp[i]){
if (mp[j] != -1) {
//check(1);
return false;
}
mp[j] = mp[i];
g[mp[i]].pb(j);
}
}
}
//check zeros:
for (ll i=0; i<n ;i++){
for (ll j=0; j<n; j++){
if (p[i][j] == 0 && mp[i] == mp[j]){
//check(0);
return false;
}
}
}
return true;
}
ll checkWhich2(ll n, ll i, vector <vi> &p, vector <vi> &g){
for (ll i= 0; i<sz(g[i]); i++){
for (ll j =0; j<n; j++){
if (p[i][j] == 2) return 2;
}
}
return 1;
}
ll construct(vector<vi> p) {
//step 0: standard validation (p[i][j] = p[j][i], p[i][i] = 1, p[i][j] < 3)
//step 1: separate into different groups/graphs and check
//step 2.1: if group contains only 1, connect using a line
//step 2.2: if group contains both 2 and/or 1: first connect lines, then form cycle (check for cycle size >= 3)
ll n= sz(p);
//step 0:
bool ok = step0(n,p);
//dbg(ok);
if (!ok) return 0;
//step 1:
vi mp(n, -1);
vector <vi> g;
ok = step1(n,p,mp,g);
//dbg(ok);
if (!ok) return 0;
//printVct2D(g);
//step 2:
vector <vi> ans(n,vi());
for (ll i= 0; i<n; i++) ans[i].assign(n, 0);
vi vis, v;
for (ll k= 0; k<sz(g); k++){
//check
ll c2 = checkWhich2(n,k,p,g);
ll c, prev;
if (c2 == 1){ //2.1
for (ll i= 1; i<sz(g[k]); i++){
prev = g[k][i-1];
c = g[k][i];
ans[prev][c] = 1;
ans[c][prev] = 1;
}
}
else{ //2.2
// v.clear();
// vis.assign(n, 0);
// for (ll i = 0; i<sz(g[k]); i++){
// c = g[k][i];
// if (vis[c]) continue;
// v.pb(c);
// vis[c] = 1;
// for (ll j=0; j<n; j++){
// if (c == j) continue;
// if (p[c][j] == 1){
// ans[c][j] = 1;
// ans[j][c] = 1;
// vis[j] = 1;
// }
// }
// }
for (ll i =0; i<sz(g[k]); i++){
c = g[k][i];
v.pb(c);
}
// printVct2D(ans);
// printVct(v);
//dbg(sz(v));
if (sz(v) <= 2){ //minimm cycle size = 3
//check(2);
ok = false;
break;
}
c = v[0], prev = v.back();
ans[c][prev] = 1;
ans[prev][c] = 1;
for (ll i=1; i<sz(v); i++){
c = v[i];
prev = v[i-1];
ans[c][prev] = 1;
ans[prev][c] = 1;
}
//printVct2D(ans);
}
}
if (!ok) return 0;
build(ans);
return 1;
}
/*
*/
