#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int construct(vector<vector<int>> p)
{
int N = p.size();
for (int i=0;i<N;i++) for (int j=0;j<N;j++) if (p[i][j] == 3) return 0;
vector<vector<int>> answer(N, vector<int>(N, 0));
// union-find
vector<int> line(N, 0), compo(N, 0);
for (int i=0;i<N;i++) line[i] = compo[i] = i;
function<int(int, vector<int>&)> find;
find = [&](int n, vector<int> &par){
return par[n] == n ? n : par[n] = find(par[n], par);
};
auto _union = [&](vector<int> &par, int a, int b){
par[find(b, par)] = find(a, par);
};
for (int i=0;i<N;i++) for (int j=i+1;j<N;j++){
if (p[i][j]) _union(compo, i, j);
if (p[i][j] == 1) _union(line, i, j);
}
for (int i=0;i<N;i++) find(i, compo), find(i, line);
auto connect = [&](int a, int b){ answer[a][b] = answer[b][a] = 1; };
for (int i=0;i<N;i++) if (compo[i] == i){
vector <int> cycle;
for (int j=0;j<N;j++) if (compo[j] == i && line[j] == j) cycle.push_back(j);
int n = cycle.size();
if (n == 1) continue;
if (n == 2) return 0;
for (int j=0;j<n;j++) connect(cycle[j], cycle[(j+1)%n]);
}
for (int i=0;i<N;i++) if (line[i] != i) connect(line[i], i);
for (int i=0;i<N;i++) for (int j=i+1;j<N;j++){
if (line[i] == line[j]){
if (p[i][j] != 1) return 0;
}
else if (compo[i] == compo[j]){
if (p[i][j] != 2) return 0;
}else{
if (p[i][j] != 0) return 0;
}
}
build(answer);
return 1;
}
