#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef unordered_set<int> us;
int p1[1010],cc[1010];
void init(int n){
for(int i=0;i<n;i++) p1[i]=cc[i]=i;
}
int findset(int x,int sw){
if(sw==1){
if(p1[x]==x) return x;
return p1[x]=findset(p1[x],sw);
}
else{
if(cc[x]==x) return x;
return cc[x]=findset(cc[x],sw);
}
}
bool issameset(int i,int j,int sw){
return findset(i,sw)==findset(j,sw);
}
void unionset(int i,int j,int sw){
if(!issameset(i,j,sw)){
int x=findset(i,sw),y=findset(j,sw);
if(sw==1){
p1[x]=y;
}
else{
cc[x]=y;
}
}
}
int construct(std::vector<std::vector<int>> p) {
vector<vi> bu;
int n=p.size();
bu.resize(n);
init(n);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) bu[i].push_back(0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]!=0){
if(p[i][j]==1) unionset(i,j,1);
unionset(i,j,2);
}
}
}
vi an;
an.assign(n,-1);
for(int i=0;i<n;i++){
if(an[findset(i,1)]==-1){
an[findset(i,1)]=i;
}
else{
int a=an[findset(i,1)];
bu[a][i]=bu[i][a]=1;
an[findset(i,1)]=i;
}
}
vector<us> ul,pr;
ul.resize(n);
pr.resize(n);
for(int i=0;i<n;i++){
pr[findset(i,2)].insert(findset(i,1));
}
/* for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) cout<<bu[i][j]<<" ";
cout<<endl;
}*/
for(int i=0;i<n;i++){
if(pr[i].empty()) continue;
int ant=-1,pi;
for(auto &v:pr[i]){
if(ant==-1){
pi=v;
ant=v;
}
else{
bu[ant][v]=bu[v][ant]=1;
ant=v;
}
}
bu[pi][ant]=bu[ant][pi]=1;
}
build(bu);
return 1;
}
