#include "supertrees.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>parent;
int find(int p){
if (parent[p]==p) return p;
else return parent[p]=find(parent[p]);
}
void unite(int p1, int p2){
p1=find(p1); p2=find(p2);
parent[p1]=p2;
return;
}
int construct(vector<vector<int> > p) {
int n=p.size();
parent.resize(n);
for (int i=0; i<n; i++) parent[i]=i;
vector<vector<int> >answer(n, vector<int>(n, 0));
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (p[i][j]==1){
if (find(i)!=find(j)){
for (int k=0; k<n; k++){
if (p[i][k]!=p[j][k]) return 0;
}
answer[i][j]=1;
answer[j][i]=1;
unite(i, j);
}
}
}
}
vector<int>c;
for (int i=0; i<n; i++){
if (parent[i]==i) c.push_back(i);
}
for (int i: c){
for (int j: c){
if (p[i][j]==3) return 0;
else if (p[i][j]==2){
if (find(i)!=find(j)) unite(i, j);
}
}
}
for (int i: c){
int ant=i;
int ant2=-1;
for (int j: c){
if (find(j)==i && i!=j){
if (ant2==-1) ant2=j;
answer[j][ant]=1;
answer[ant][j]=1;
ant=j;
}
}if (ant2==ant) return 0;
if (ant!=i){
answer[i][ant]=1;
answer[ant][i]=1;
}
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (p[i][j]==0 && find(i)==find(j)) return 0;
}
}
build(answer);
return 1;
}
