#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int construct(std::vector<std::vector<int>> p)
{
int N = p.size();
vi comp(N, -1);
vvi ans(N, vi(N, 0));
for (int v = 0; v < N; ++v)
{
if (comp[v] == -1)
{
vvi c(4);
comp[v] = v;
for (int u = 0; u < N; ++u)
{
if (p[v][u] == 0 || u == v)
continue;
if (comp[u] != -1)
return 0;
comp[u] = v;
c[p[v][u]].push_back(u);
}
if (sz(c[2]) && sz(c[3]))
return 0;
for (int u : c[1])
{
ans[v][u] = ans[u][v] = 1;
for (int w = 0; w < N; ++w)
if (comp[w] != comp[u] && p[u][w] > 0)
return 0;
for (int w : c[1])
if (p[u][w] != 1)
return 0;
for (int w : c[2])
if (p[u][w] != 2)
return 0;
for (int w : c[3])
if (p[u][w] != 3)
return 0;
}
if (!c[2].empty())
{
for (int u : c[2])
for (int w = 0; w < N; ++w)
if (comp[w] != comp[u] && p[u][w] > 0)
return 0;
int last = v;
vi belongs(sz(c[2]), -1);
for (int i = 0; i < sz(c[2]); ++i)
{
int u = c[2][i];
if (belongs[i] == -1)
{
ans[last][u] = ans[u][last] = 1;
last = u;
belongs[i] = u;
}
for (int j = i + 1; j < sz(c[2]); ++j)
{
int w = c[2][j];
if (p[u][w] == 1)
{
if (belongs[j] != -1)
{
if (belongs[j] != belongs[i])
return 0;
}
else
{
belongs[j] = belongs[i];
ans[w][u] = ans[u][w] = 1;
}
}
else if (p[u][w] == 2)
{
if (belongs[i] == belongs[j])
return 0;
}
else
return 0;
}
}
if (ans[v][last])
return 0;
ans[v][last] = ans[last][v] = 1;
}
}
}
build(ans);
return 1;
}
