#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int pa[1000];
int _find(int x){
if(x == pa[x]) return x;
return pa[x] = _find(pa[x]);
}
void _union(int x, int y){
x = _find(x); y = _find(y);
pa[y] = x;
}
int construct(std::vector<std::vector<int>> p){
int n = p.size();
iota(pa, pa + n, 0);
vector<int> vis(n, 0);
vector<vector<int>> ln, cyc, cycid, ans(n, vector<int>(n, 0));
for(int i = 0;i<n;i++){
if(!vis[i]){
vis[i] = 1;
ln.push_back({i});
for(int j = i + 1;j<n;j++){
if(p[i][j] == 1) ln.back().push_back(j), vis[j] = 1;
else if(p[i][j] == 3) return 0;
}
}
}
int m = ln.size();
for(int i = 0;i<n;i++) vis[i] = 0;
for(int i = 0;i<m;i++){
if(!vis[ln[i][0]]){
vis[ln[i][0]] = 1;
cyc.push_back({ln[i][0]});
cycid.push_back({i});
for(int j = i + 1;j<m;j++){
if(p[ln[i][0]][ln[j][0]] == 2) cyc.back().push_back(ln[j][0]), vis[ln[j][0]] = 1, cycid.back().push_back(j);
}
}
}
for(int i = 0;i<m;i++){
for(int j = 0;j<ln[i].size() - 1;j++){
ans[ln[i][j]][ln[i][j + 1]] = ans[ln[i][j + 1]][ln[i][j]] = 1;
_union(ln[i][j], ln[i][j + 1]);
}
}
for(int i = 0;i<cyc.size();i++){
for(int j = 0;j<cyc[i].size() - 1;j++){
ans[cyc[i][j]][cyc[i][j + 1]] = ans[cyc[i][j + 1]][cyc[i][j]] = 1;
_union(cyc[i][j], cyc[i][j + 1]);
}
if(cyc[i].size() != 1) ans[cyc[i][0]][cyc[i].back()] = ans[cyc[i].back()][cyc[i][0]] = 1, _union(cyc[i].back(), cyc[i][0]);
if(cyc[i].size() == 2) return 0;
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if((p[i][j] && _find(i) != _find(j)) || (!p[i][j] && _find(i) == _find(j))) return 0;
}
}
for(int i = 0;i<m;i++){
for(auto x : ln[i]){
for(auto y : ln[i]){
if(p[x][y] != 1) return 0;
}
}
}
for(int i = 0;i<cyc.size();i++){
for(auto x : cyc[i]){
for(auto y : cyc[i]){
if(x != y && p[x][y] != 2) return 0;
}
}
for(auto x : cycid[i]){
for(auto y : cycid[i]){
if(x != y){
for(auto X : ln[x]) for(auto Y : ln[y]) if(p[X][Y] != 2) return 0;
}
}
}
}
build(ans);
return 1;
}
