#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e3 + 10;
int n,P[N];
vector<int> vec[N],cy[N];
int gp(int x){
return P[x]!=-1?P[x]=gp(P[x]):x;
}
void uni(int v, int u){
v=gp(v);
u=gp(u);
if(v==u) return;
P[u]=v;
}
int construct(vector<vector<int>> p) {
memset(P,-1,sizeof P);
n = p.size();
vector<vector<int>> ans(n,vector<int>(n,0));
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
if(p[i][j]==1) uni(i,j);
if(p[i][j]==3) return 0;
}
}
for(int i=0; i<n; i++) vec[gp(i)].pb(i);
memset(P,-1,sizeof P);
for(int i=0; i<n; i++){
for(int j : vec[i]){
if(j!=i) ans[i][j]=ans[j][i]=1;
for(int k : vec[i]) if(p[j][k]!=1) return 0;
}
for(int j=0; j<n; j++){
if(i==j) continue;
bool f=0,g=0;
for(int x : vec[i]){
for(int y : vec[j]){
if(p[x][y]==2) f=1;
if(p[x][y]==0) g=1;
}
}
if(f && g) return 0;
if(f) uni(i,j);
}
}
for(int i=0; i<n; i++) if(!vec[i].empty()){
cy[gp(i)].pb(i);
}
for(int i=0; i<n; i++){
for(int a : cy[i]){
for(int b : cy[i]){
if(a==b) continue;
for(int x : vec[a]){
for(int y : vec[b]){
if(p[x][y]!=2) return 0;
}
}
}
}
if((int)cy[i].size()==2) return 0;
if((int)cy[i].size()<3) continue;
int ls = i;
for(int j : cy[i]){
if(j==i) continue;
ans[ls][j]=ans[j][ls]=1;
ls=j;
}
ans[ls][i]=ans[i][ls]=1;
}
build(ans);
return 1;
}
