#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int a,B[500005],B1[500005];
vector <int> v[500005],v1[500005],v2;
int get_col(int x) {
if(B[x]==x) return x;
B[x]=get_col(B[x]);
return B[x];
}
void col(int x,int y) {
B[get_col(x)]=get_col(y);
}
int get_col1(int x) {
if(B1[x]==x) return x;
B1[x]=get_col1(B1[x]);
return B1[x];
}
void col1(int x,int y) {
B1[get_col1(x)]=get_col1(y);
}
int construct(vector < vector < int > > p) {
int n = p.size();
vector < vector < int > > answer(n, vector < int >(n, 0));
for (int i = 0; i < n; i++) {
B[i]=i;
B1[i]=i;
for(int j=0;j<n;j++) {
if(p[i][j]==3) return 0;
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(p[i][j]!=0) col(i,j);
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(get_col(i)==get_col(j) && p[i][j]==0) return 0;
}
}
for(int i=0;i<n;i++) {
v[get_col(i)].push_back(i);
}
for(int i=0;i<n;i++) {
if(v[i].size()==0) continue;
a=0;
for(int j=0;j<v[i].size();j++) {
for(int l=0;l<v[i].size();l++) {
if(p[v[i][j]][v[i][l]]==2) a=1;
else col1(v[i][j],v[i][l]);
}
}
if(a==0) {
for(int j=1;j<v[i].size();j++) {
answer[v[i][j-1]][v[i][j]]=1;
answer[v[i][j]][v[i][j-1]]=1;
}
}
else {
for(int i=0;i<v[i].size();i++) {
for(int j=0;j<v[i].size();j++) {
if(get_col1(i)==get_col1(j) && p[i][j]==2) return 0;
}
}
for(int j=0;j<v[i].size();j++)
v1[get_col1(v[i][j])].push_back(v[i][j]);
v2.clear();
for(int j=0;j<v[i].size();j++) {
if(v1[v[i][j]].size()==0) continue;
v2.push_back(v1[v[i][j]][0]);
for(int l=1;l<v1[v[i][j]].size();l++) {
answer[v1[v[i][j]][l-1]][v1[v[i][j]][l]]=1;
answer[v1[v[i][j]][l]][v1[v[i][j]][l-1]]=1;
}
}
if(v2.size()==2) return 0;
for(int j=0;j<v2.size();j++) {
if(j==v2.size()-1) {
answer[v2[0]][v2[j]]=1;
answer[v2[j]][v2[0]]=1;
}
else {
answer[v2[j+1]][v2[j]]=1;
answer[v2[j]][v2[j+1]]=1;
}
}
for(int j=0;j<v[i].size();j++)
v1[get_col1(v[i][j])].clear();
}
}
build(answer);
/*for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
cout<<answer[i][j]<<" ";
}
cout<<endl;
}*/
return 1;
}/*
int main() {
//cout<<construct({ {1,0} , {0,1} });
cout<<construct({ {1,1,2,2} , {1,1,2,2} , {2,2,1,2} , {2,2,2,1} });
//1,1,2,2
//1,1,2,2
//2,2,1,2
//2,2,2,1
}*/
