#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int par[N],sz[N],a[N][N],ans[N][N],type[N],k,i,n,u,v,x,y,fix[N],cycle[N];
vector<int> comp[N],V[N],E;
vector<vector<int> > answer;
int find_parent(int u){
if(par[u]==u) return u;
return par[u]=find_parent(par[u]);
}
void merge(int u,int v){
u=find_parent(u);
v=find_parent(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
par[v]=u;
sz[u]+=sz[v];
}
void Go(int u){
for(k=0;k<comp[u].size();k++){
for(i=k+1;i<comp[u].size();i++){
int x=comp[u][k];
int y=comp[u][i];
if(a[x][y]==1){
V[x].push_back(y);
V[y].push_back(x); }
}
}
E.clear();
for(k=0;k<comp[u].size();k++){
x=comp[u][k];
if(fix[x]) continue;
E.push_back(x);
type[x]=1;
if(!fix[x]){
for(i=0;i<V[x].size();i++){
fix[V[x][i]]=x;
ans[x][V[x][i]]=ans[V[x][i]][x]=1;
}
}
}
if(E.size()>1){
for(k=0;k<E.size();k++){
ans[E[k]][E[(k+1)%E.size()]]=ans[E[(k+1)%E.size()]][E[k]]=1;
}
}
}
bool check(){
for(k=1;k<=n;k++){
std::vector<int> row;
for(i=1;i<=n;i++){
if(i==k) ans[k][i]=0;
else {
int x=find_parent(k);
int y=find_parent(i);
if(a[k][i]==0 && x==y)return 0;
if(!type[k] && !type[i] && a[k][i]==2 && fix[k]==fix[i]) return 0;
}
row.push_back(ans[k][i]);
}answer.push_back(row);
}
return 1;
}
int construct(std::vector<std::vector<int> > v){
//[[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]]
n=v.size();
for(k=1;k<=n;k++)
par[k]=k,sz[k]=1;
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
a[k][i]=v[k-1][i-1];
// cout<<a[k][i]<<" ";
if(a[k][i]==3) {
return 0;
}
if(a[k][i]!=0) merge(k,i);
}
// cout<<endl;
}
for(k=1;k<=n;k++){
comp[find_parent(k)].push_back(k);
}
for(int k=1;k<=n;k++){
Go(k);
if(E.size()==2 && a[E[0]][E[1]]==2) return 0;
}
if(!check()) return 0;
build(answer);
return 1;
}
