#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int p1[1010],tam[1010],cc[1010];
void init(int n){
for(int i=0;i<n;i++){
p1[i]=i;
cc[i]=i;
tam[i]=1;
}
}
int findset(int x,int sw){
if(sw==1){
if(p1[x]==x) return x;
return p1[x]=findset(p1[x],sw);
}
if(sw==2){
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;
tam[y]+=tam[x];
}
if(sw==2){
cc[x]=y;
}
}
}
int construct(std::vector<std::vector<int>> p) {
vector<vi> bu;
vector<vi> dt;
int n=p.size();
bu.resize(n);
dt.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]!=p[j][i]) return 0;
if(i==j){
if(p[i][j]==0 or p[i][j]==2) return 0;
continue;
}
if(p[i][j]==2 or p[i][j]==1){
if(p[i][j]==1)unionset(i,j,1);
unionset(i,j,2);
}
else{
dt[i].push_back(j);
dt[j].push_back(i);
}
}
}
/*for(int i=0;i<n;i++) cout<<p1[findset(i,1)]<<" ";
cout<<endl;
for(int i=0;i<n;i++) cout<<cc[findset(i,2)]<<" ";
cout<<endl;*/
/* for(int i=0;i<dt.size();i++){
for(int j=0;j<dt[i].size();j++){
if(issameset(i,dt[i][j],1) or issameset(i,dt[i][j],2)){
return 0;
}
}
}
for(int i=0;i<n;i++){
if(tam[findset(i,2)]==2){
return 0;
}
}*/
vi in,ul;
in.assign(n,-1);
ul.assign(n,-1);
for(int i=0;i<n;i++){
if(in[findset(i,1)]==-1){
in[findset(i,1)]=i;
ul[findset(i,1)]=i;
}
else{
int a=in[findset(i,1)];
bu[a][i]=bu[i][a]=1;
ul[findset(i,1)]=1;
}
}
set<int> s;
for(int i=0;i<n;i++) s.insert(findset(i,2));
/*for(int i=0;i<n;i++) cout<<in[findset(i,1)]<<" ";
cout<<endl;
for(int i=0;i<n;i++) cout<<ul[findset(i,1)]<<" ";
cout<<endl;*/
for(auto &v:s){
set<int> c1,c2;
for(int i=0;i<n;i++){
if(findset(i,2)==v){
if(tam[findset(i,1)]!=1)c1.insert(findset(i,1));
else c2.insert(i);
}
}
/*for(auto &j:c1) cout<<j<<" ";
cout<<endl;
for(auto &j:c2) cout<<j<<" ";
cout<<endl;*/
auto it=c1.begin();
int ant=ul[findset((*it),1)];
for(auto &j:c2){
bu[ant][j]=bu[j][ant]=1;
ant=j;
}
it++;
int aux;
if(it==c1.end()){
aux=ant;
}
else{
aux=in[findset((*it),1)];
}
ant=ul[findset((*c1.begin()),1)];
bu[ant][aux]=bu[aux][ant]=1;
}
build(bu);
return 1;
}
