#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
//#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pb push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define inf 0x3f3f3f3f3f3f3f3f
#define pow2(x) (1ll<<(x))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif
const int maxn=1005;
struct dsu{
int par[maxn];
dsu(){rep(maxn) par[i]=i;}
int Find(int x){return x==par[x]?x:par[x]=Find(par[x]);}
void Union(int x, int y){
x=Find(x),y=Find(y);
if(x==y) return;
par[x]=y;
}
};
int construct(vector<vector<int>> p){
int n=sz(p);
vector<vector<int>> res;
res.resize(n);
rep(n) res[i].resize(n);
dsu d1,d2;
rep(n) rep1(j,n) if(p[i][j]) d1.Union(i,j);
rep(n) rep1(j,n) if(!p[i][j]) if(d1.Find(i)==d1.Find(j)) return 0;
rep(n) rep1(j,n) if(p[i][j]==3) return 0;
vector<int> vec[maxn],vec1[maxn];
rep(n) vec[d1.Find(i)].pb(i);
auto make_edge=[&](int u, int v){
res[u][v]=res[v][u]=1;
return;
};
rep(n) if(sz(vec[i])>1){
for(auto j: vec[i]) for(auto k: vec[i]) if(p[j][k]==1) d2.Union(j,k);
for(auto j: vec[i]) for(auto k: vec[i]) if(p[j][k]!=1) if(d2.Find(j)==d2.Find(k)) return 0;
for(auto j: vec[i]) vec1[j].clear();
for(auto j: vec[i]) vec1[d2.Find(j)].pb(j);
for(auto j: vec[i]) rep1(k,sz(vec1[j])-1) make_edge(vec1[j][k],vec1[j][k+1]);
vector<int> tmp;
for(auto j: vec[i]) if(sz(vec1[j])) tmp.pb(j);
if(sz(tmp)==2){
int x,y;
if(sz(vec1[tmp[0]])>1) x=tmp[0],y=tmp[1];
else if(sz(vec1[tmp[1]])>1) x=tmp[1],y=tmp[0];
else return 0;
make_edge(vec1[x][0],vec1[y][0]);
make_edge(vec1[x][1],vec1[y][0]);
}
else{
rep1(j,sz(tmp)-1) make_edge(vec1[tmp[j]][0],vec1[tmp[j+1]][0]);
make_edge(vec1[tmp[0]][0],vec1[tmp.back()][0]);
}
}
build(res);
return 1;
}
