#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int pai[maxn];
vector<int>cmp[maxn], vontade[maxn];
int find(int a){
if(a==pai[a]) return a;
return pai[a]=find(pai[a]);
}
void merge(int a, int b){
a=find(a); b=find(b);
if(a==b) return;
if(cmp[a]<cmp[b]) swap(a,b);
for(int x : cmp[b]) cmp[a].push_back(x);
for(int x : vontade[b]) vontade[a].push_back(x);
pai[b]=a;
cmp[b].clear();
vontade[b].clear();
}
int construct(vector<vector<int>> p){
int n=p.size();
for(int i=0;i<n;i++){
pai[i]=i;
cmp[i].push_back(i);
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) if(p[i][j]==1) merge(i,j);
//cout << "obvio" << endl;
// juntei tds os caras q formarão as árvoes
vector<vector<int>>ans(n,vector<int>(n,0));
for(int i=0;i<n;i++){
int last=-1;
for(int x : cmp[i]){
if(last!=-1) ans[x][last]=ans[last][x]=1;
for(int y : cmp[i]) if(x!=y&&p[x][y]!=1) return 0;
last=x;
}
for(int x : cmp[i]) vontade[i].push_back(x);
cmp[i].clear();
cmp[i].push_back(i);
}
//cout << "eh" << endl;
// chequei se não tinha incongruencias
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(p[i][j]==2){
int a=find(i), b=find(j);
if(a==b) continue;
for(int x : vontade[a])
for(int y : vontade[b]) if(x!=y&&p[x][y]!=2) return 0;
merge(a,b);
}
}
//cout << "wow" << endl;
for(int i=0;i<n;i++){
if(cmp[i].size()==2) return 0;
if(cmp[i].size()<=2) continue;
int first=cmp[i][0], last=-1;
for(int x : cmp[i]){
if(last!=-1) ans[x][last]=ans[last][x]=1;
last=x;
}
ans[last][first]=ans[first][last]=1;
}
//cout << "ah n" << endl;
build(ans);
return 1;
}
