#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;
vvi cycle;
vi C2(all(c[2]));
while (!C2.empty())
{
int u = C2.back();
C2.pop_back();
cycle.push_back({u});
int end = sz(C2);
for (int i = 0; i < end;)
{
int w = C2[i];
if (p[u][w] == 2)
++i;
else if (p[u][w] == 1)
{
cycle.back().push_back(w);
swap(C2[i], C2[--end]);
C2.pop_back();
}
}
}
// checks
if (sz(cycle) <= 1)
return 0;
for (int i = 0; i < sz(cycle); ++i)
{
for (int u : cycle[i])
for (int w : cycle[i])
if (p[u][w] != 1)
return 0;
for (int j = i + 1; j < sz(cycle); ++j)
for (int u : cycle[i])
for (int w : cycle[j])
if (p[u][w] != 2)
return 0;
}
// build
int last = v;
for (int i = 0; i < sz(cycle); ++i)
{
int u = cycle[i][0];
ans[last][u] = ans[u][last] = 1;
last = u;
for (int j = 1; j < sz(cycle[i]); ++j)
ans[u][cycle[i][j]] = ans[cycle[i][j]][u] = 1;
}
ans[last][v] = ans[v][last] = 1;
}
}
}
build(ans);
return 1;
}
