#include "supertrees.h"
#include <vector>
#include <map>
int dsu0[1010];
int dsu1[1010];
int findSet0(int a){
if(dsu0[a]==a)return a;
else return dsu0[a]=findSet0(dsu0[a]);
}
void unionSet0(int a,int b){
int A = findSet0(a);
int B = findSet0(b);
if(A==B)return;
dsu0[A]=B;
}
int findSet1(int a){
if(dsu0[a]==a)return a;
else return dsu0[a]=findSet0(dsu0[a]);
}
void unionSet1(int a,int b){
int A = findSet0(a);
int B = findSet0(b);
if(A==B)return;
dsu0[A]=B;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i=0;i<=1000;i++){
dsu0[i]=i;
dsu1[i]=i;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
if(p[i][j]==1)continue;
else return 0;
}
if(p[i][j]>0)unionSet0(i,j);
if(p[i][j]==3)return 0;
if(p[i][j]==0&&findSet0(i)==findSet0(j))return 0;
}
}
std::map<int,std::vector<int>> m;
for(int i=0;i<n;i++){
m[findSet0(i)].push_back(i);
}
for(auto& [id,com]:m){
for(int ci=0;ci<com.size();ci++){
for(int cj=0;cj<com.size();cj++){
if(ci==cj)continue;
int i = com[ci];
int j = com[cj];
if(p[i][j]==1)unionSet1(i,j);
if(p[i][j]==2&&findSet1(i)==findSet1(j))return 0;
}
}
for(int ci=0;ci<com.size();ci++){
for(int cj=0;cj<com.size();cj++){
int i = com[ci];
int j = com[cj];
if(p[i][j]==2){
answer[i][j]=answer[j][i]=1;
}
if(p[i][j]==1){
answer[i][findSet1(j)]=1;
answer[j][findSet1(i)]=1;
answer[findSet1(j)][i]=1;
answer[findSet1(i)][j]=1;
}
}
}
}
for(int i=0;i<n;i++)answer[i][i]=0;
build(answer);
return 1;
}
