#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
vector<vector<int>> g;
vector<bool> vis;
vector<vector<int>> checkz;
vector<bool> d;
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 cur = 0;
void dfs(int k, bool cyc){
if(d[k]){
cyc = true;
}
if(cyc){
checkz[cur][k] = 2;
checkz[k][cur] = 2;
}else{
checkz[cur][k] = 1;
checkz[k][cur] = 1;
}
vis[k] = true;
for(int y = 0; y < g[k].size(); y++){
if(vis[g[k][y]]) continue;
dfs(g[k][y], cyc);
}
}
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);
}
}
}
d.clear();
d.resize(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){
if(d[par[y]]) return 0;
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;
}
}
checkz.clear();
checkz.resize(n, vector<int>(n));
g.resize(n);
vis.resize(n);
for(int i = 0; i < n; i++){
for(int y = 0; y < n; y++){
if(i == y) continue;
if(answer[i][y] == 1){
g[i].push_back(y);
}
}
}
cur = 0;
for(;cur < n; cur++){
vis.clear();
vis.resize(n);
dfs(cur, false);
checkz[cur][cur] = 1;
}
if(checkz != p) return 0;
build(answer);
return 1;
}
