#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;
const int maxn=(1<<20);
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;
struct DSU{
vector<int> par;
DSU(int n){
par.resize(n);
iota(par.begin(),par.end(),0);
}
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x!=y)par[x]=y;
}
};
int construct(vector<vector<int>> p){
int n=p.size();
vector<vector<int> > b(n,vector<int>(n,0));
F(i,0,n){
F(j,0,n)if(p[i][j]==3)return 0;
}
DSU uf1(n);
F(i,0,n){
F(j,0,n){
if(p[i][j])uf1.merge(i,j);
}
}
F(i,0,n){
F(j,0,n){
if((uf1.find(i)==uf1.find(j))!=(p[i][j]>0))return 0;
}
}
vector<vector<int> > comps(n);
F(i,0,n)comps[uf1.find(i)].pb(i);
F(c,0,n){
if(comps[c].empty())continue;
const vector<int>& nodes=comps[c];
DSU uf2(n);
for(int i:nodes){
for(int j:nodes){
if(p[i][j]==1)uf2.merge(i,j);
}
}
vector<int> reps;
vector<bool> seen(n,0);
for(int i:nodes){
int rt=uf2.find(i);
if(!seen[rt]){
seen[rt]=1;
reps.pb(rt);
vector<int> group;
for(int j:nodes){
if(uf2.find(j)==rt)group.pb(j);
}
for(int k=0;k+1<group.size();++k){
int u=group[k],v=group[k+1];
b[u][v]=b[v][u]=1;
}
}
}
for(int i:nodes){
for(int j:nodes){
if(uf2.find(i)==uf2.find(j)){
if(p[i][j]!=1)return 0;
}else{
if(p[i][j]!=2)return 0;
}
}
}
int m=reps.size();
if(m==2)return 0;
if(m>=3){
F(k,0,m){
int u=reps[k],v=reps[(k+1)%m];
b[u][v]=b[v][u]=1;
}
}
}
build(b);
return 1;
}
