#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int fpar(int k){
if(par[k] == k){
return k;
}
par[k] = fpar(par[k]);
return par[k];
}
void merge(int k, int f){
k = fpar(k);
f = fpar(f);
par[k] = f;
}
int construct(vector<vector<int>> p) {
int n = p.size();
par.resize(n);
for(int i = 0; i < n; i++){
par[i] = i;
}
vector<std::vector<int>> answer(n, vector<int>(n));
for(int i = 0; i < n; i++){
for(int y = 0; y < n; y++){
if(i == y) continue;
if(p[i][y] == 3){
return 0;
}
if(p[i][y] == 1){
if(fpar(i) == fpar(y)) continue;
answer[i][y] = 1;
answer[y][i] = 1;
merge(i, y);
}
}
}
vector<bool> d(n);
for(int i = 0; i < n; i++){
if(par[i] != i || d[i]) continue;
vector<int> j;
for(int y = 0; y < n; y++){
if(i == y) continue;
if(p[i][y] == 2){
j.push_back(par[y]);
}
}
sort(j.begin(), j.end());
j.erase(unique(j.begin(), j.end()), j.end());
for(auto y : j){
d[y] = true;
}
j.push_back(i);
if(j.size() == 2){
return 0;
}
if(j.size() == 1) continue;
answer[j[0]][j.back()] = 1;
answer[j.back()][j[0]] = 1;
for(int y = 1; y < j.size(); y++){
answer[j[y]][j[y-1]] = 1;
answer[j[y-1]][j[y]] = 1;
}
}
// vector<vector<int>> checkz(n, vector<int>(n));
// if(checkz != p) return 0;
build(answer);
return 1;
}
