#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 1e3+5;
const int INF = 1e9;
int n, dsu[nx], dsu2[nx];
vector<vector<int>> b;
vector<int> cycle[nx];
int find(int x, int* d)
{
if(d[x] == x) return x;
d[x] = find(d[x], d);
return d[x];
}
void merge(int u, int v, int* d)
{
int pu = find(u, d), pv = find(v, d);
if(pu != pv) d[pu] = pv;
}
int construct(vector<vector<int>> p)
{
n = p.size();
iota(dsu, dsu + nx, 0);
iota(dsu2, dsu2 + nx, 0);
b.assign(n, vector<int> (n, 0));
// dsu2 -> connect the component together
// dsu -> connect only tree
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i == j) continue;
if(p[i][j] != p[j][i] || p[i][j] == 3) return 0;
if(p[i][j] > 0) merge(i, j, dsu2);
if(p[i][j] == 1) merge(i, j, dsu);
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(i == j) continue;
if(find(i, dsu) == find(j, dsu) && p[i][j] != 1) return 0;
if(find(i, dsu2) == find(j, dsu2) && p[i][j] == 0) return 0;
}
}
for(int i=0;i<n;i++) {
int root = find(i, dsu);
if(i != root) {
b[i][root] = b[root][i] = 1;
}
}
for(int i=0;i<n;i++) {
if(i == find(i, dsu)) {
cycle[find(i, dsu2)].push_back(i);
}
}
for(int i=0;i<n;i++) {
int sz = cycle[i].size();
if(sz <= 1) continue;
if(sz == 2) return 0;
for(int j=0;j<sz;j++) {
int u = cycle[i][j];
int v = cycle[i][(j + 1) % sz];
b[u][v] = b[v][u] = 1;
}
}
build(b);
return 1;
}
