#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
struct DSU{
vector<int>e;
vector<int>storage[1005];
void init(int n){
e=vector<int>(n,-1);
for(int x=0;x<n;x++){
storage[x].push_back(x);
}
}
int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
bool sameSet(int x, int y){return get(x)==get(y);}
int size(int x){return -e[get(x)];}
bool unite(int x, int y){
x=get(x);
y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
for(auto it:storage[y]) storage[x].push_back(it);
e[y]=x;
return 1;
}
};
int construct(vector<vector<int>> p) {
int n=p.size();
DSU one;
one.init(n+5);
DSU two;
two.init(n+5);
DSU three;
three.init(n+5);
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
if(p[x][y]==1){
one.unite(x,y);
}
else if(p[x][y]==2){
two.unite(x,y);
}
else if(p[x][y]==3){
three.unite(x,y);
}
}
}
vector<vector<int>>ans;
ans.resize(n);
for(int x=0;x<n;x++){
for(int y=0;y<n;y++){
ans[x].push_back(0);
}
}
bool done[n+5];
memset(done,0,sizeof(done));
for(int x=0;x<n;x++){
if(one.get(x)==x){
int last=-1;
for(auto it:one.storage[x]){
if(last!=-1){
ans[last][it]=1;
ans[it][last]=1;
done[it]=true;
}
last=it;
}
for(auto it:one.storage[x]){
for(auto it2:one.storage[x]){
if(p[it][it2]!=1) return 0;
}
}
}
}
for(int x=0;x<n;x++){
if(two.get(x)==x&&two.size(x)>1){
if(two.size(x)==2) return 0;
int last=-1;
for(auto it:two.storage[x]){
if(done[it]) continue;
if(last!=-1){
ans[last][it]=1;
ans[it][last]=1;
}
last=it;
}
if(last!=-1){
ans[last][two.storage[x][0]]=1;
ans[two.storage[x][0]][last]=1;
}
for(auto it:two.storage[x]){
for(auto it2:two.storage[x]){
if(it==it2) continue;
if(one.sameSet(it,it2)) continue;
if(p[it][it2]!=2) return 0;
}
}
}
}
for(int x=0;x<n;x++){
if(three.get(x)==x&&three.size(x)>1){
if(three.size(x)<=3) return 0;
int last=-1;
for(auto it:three.storage[x]){
if(done[it]) continue;
if(last!=-1){
ans[last][it]=1;
ans[it][last]=1;
}
last=it;
}
if(last!=-1){
ans[last][three.storage[x][0]]=1;
ans[three.storage[x][0]][last]=1;
ans[last][three.storage[x][1]]=1;
ans[three.storage[x][1]][last]=1;
}
for(auto it:three.storage[x]){
for(auto it2:three.storage[x]){
if(it==it2) continue;
if(one.sameSet(it,it2)) continue;
if(two.sameSet(it,it2)) return 0;
if(p[it][it2]!=3) return 0;
}
}
}
}
build(ans);
return 1;
}
