#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
//void build(vector<vector<int> >);
struct UnionFind {
vector<int> root;
UnionFind(int N) {
root.resize(N);
fill(root.begin(),root.end(),-1);
}
int Find(int a) {
if(root[a] < 0) return a;
int r = Find(root[a]);
root[a] = r;
return r;
}
void Merge(int a, int b) {
a = Find(a);
b = Find(b);
if(a == b) return;
if(root[a] > root[b]) swap(a, b);
root[a] += root[b];
root[b] = a;
}
};
vector<vector<int> > adj;
vector<vector<int> > adj2;
int construct(vector<vector<int> > p) {
vector<vector<int> > ans;
int N = p.size();
ans.resize(N);
int i;
for(i=0;i<N;i++) ans[i].resize(N);
int j;
UnionFind UF1(N);
UnionFind UF2(N);
adj.resize(N);
adj2.resize(N);
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
if(p[i][j]==1) {
UF2.Merge(i, j);
}
if(p[i][j]) {
UF1.Merge(i, j);
}
}
}
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
if(!p[i][j]) {
}
}
}
for(i=0;i<N;i++) {
adj2[UF2.Find(i)].push_back(i);
}
for(i=0;i<N;i++) {
if(!adj2[i].empty()) {
//cout << adj2[i][0] << ' ';
adj[UF1.Find(adj2[i][0])].push_back(adj2[i][0]);
}
}
for(i=0;i<N;i++) {
int sz = adj[i].size();
//if(sz == 1) return 0;
if(sz == 2) return 0;
if(sz >= 3) {
for(j=0;j<sz-1;j++) {
ans[adj[i][j]][adj[i][j+1]] = 1;
ans[adj[i][j+1]][adj[i][j]] = 1;
}
ans[adj[i][0]][adj[i][sz-1]] = 1;
ans[adj[i][sz-1]][adj[i][0]] = 1;
}
int sz2 = adj2[i].size();
for(j=0;j<sz2-1;j++) {
ans[adj2[i][j]][adj2[i][j+1]] = 1;
ans[adj2[i][j+1]][adj2[i][j]] = 1;
}
}
build(ans);
return 1;
}
