#include "supertrees.h"
#include <vector>
using namespace std;
int frq[1005];
struct DSU{
vector<int>par,sz;
void init(int n){
par.resize(n+1);sz.resize(n+1);
for(int i=0;i<n;i++)par[i]=i,sz[i]=1;
}
int root(int u){
return par[u]==u ? u:par[u]=root(par[u]);
}
bool merge(int u,int v){
int ru=root(u),rv=root(v);
frq[u]++;
frq[v]++;
if(ru==rv)return 0;
if(sz[ru]>sz[rv])swap(sz[ru],sz[rv]);
par[ru]=rv;sz[rv]+=sz[ru];
return 1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n=p[0].size();
vector<vector<int>>v(n,vector<int>(n,0));
DSU d;d.init(n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(i==j)continue;
if(p[i][j]){
if(d.root(i)==d.root(j)&&(frq[i]==2||frq[j]==2))continue;
d.merge(i,j);
v[i][j]=1;
v[j][i]=1;
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(d.root(i)==d.root(j)&&!p[i][j])return 0;
if(p[i][j]==2&&(frq[i]!=2||frq[j]!=2))return 0;
}
}
build(v);
return 1;
}
