#include "supertrees.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int pad[2000];
int last[2000];
int vis[2000];
void init(int x){
for(int i=0;i<=x;i++){
pad[i]=i;
}
}
int findset(int i){
if(pad[i]==i)return i;
return pad[i]=findset(pad[i]);
}
bool issameset(int i,int j){
return findset(pad[i])==findset(pad[j]);
}
void unionset(int i,int j){
if(!issameset(i,j))
pad[findset(i)]=pad[findset(j)];
}
int construct(vector<vector<int>> p) {
int n = p.size();
init(n);
vector<vector<int>> answer;
for(int i=0;i<n;i++){
answer.push_back(vector<int>(n,0));
}
int cnt=0;
int pp=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==1)cnt++;
if(p[i][j]==2)pp++;
}
}
int sw=1;
if(cnt==n*n){
for(int i=0;i<n-1;i++){
answer[i][i+1]=1;
answer[i+1][i]=1;
}}
else{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==1){
unionset(i,j);
}
}
}
for(int i=0;i<n+1;i++)vis[i]=0;
map<int,vector<int>> mp;
for(int i=0;i<n;i++){
mp[findset(i)].push_back(i);
}
for(auto it=mp.begin();it!=mp.end();it++){
vector<int> aux;
aux=(*it).second;
int tm=aux.size();
for(int i=0;i<tm-1;i++){
vis[aux[i]]=1;
answer[aux[i]][aux[i+1]]=1;
answer[aux[i+1]][aux[i]]=1;
}
mp[(*it).first].clear();
}
/*for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<answer[i][j]<<" ";
}
cout<<endl;
}*/
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==2){
unionset(i,j);
}
}
}
for(int i=0;i<n;i++){
if(vis[i]==0){
mp[findset(i)].push_back(i);
}
}
for(auto it=mp.begin();it!=mp.end();it++){
vector<int> aux;
aux=(*it).second;
int tm=aux.size();
for(int i=0;i<tm-1;i++){
vis[aux[i]]=1;
answer[aux[i]][aux[i+1]]=1;
answer[aux[i+1]][aux[i]]=1;
}
if(tm>=2){
answer[aux[0]][aux[tm-1]]=1;
answer[aux[tm-1]][aux[0]]=1;
}
}}
if(sw){
build(answer);
return 1;}
else return 0;
}
