#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct Dsu
{
vector<int64_t> t;
Dsu(size_t n) { t = vector<int64_t>(n, -1); }
int64_t repr(int64_t u) { return t[u] < 0 ? u : t[u] = repr(t[u]); }
void merge(int64_t u, int64_t v)
{
u = repr(u);
v = repr(v);
if (u == v)
return;
if (t[u] > t[v])
swap(u, v);
t[u] += t[v];
t[v] = u;
}
bool same_set(int64_t u, int64_t v) { return repr(u) == repr(v); }
};
int construct(vector<vector<int>> p)
{
Dsu connected(p.size()), one_connected(p.size());
for (size_t i = 0; i < p.size(); i++)
for (size_t j = 0; j < p.size(); j++)
{
if (p[i][j] == 3)
return 0;
if (p[i][j])
connected.merge(i, j);
if (p[i][j] == 1)
one_connected.merge(i, j);
}
for (size_t i = 0; i < p.size(); i++)
for (size_t j = 0; j < p.size(); j++)
{
if ((p[i][j] == 0 && connected.same_set(i, j)) ||
(p[i][j] != 0 && !connected.same_set(i, j)))
return 0;
if ((p[i][j] == 1 && !one_connected.same_set(i, j)) ||
(p[i][j] != 1 && one_connected.same_set(i, j)))
return 0;
if ((p[i][j] == 2 && !(connected.same_set(i, j) && !one_connected.same_set(i, j))) ||
(p[i][j] != 2 && connected.same_set(i, j) && !one_connected.same_set(i, j)))
return 0;
}
vector<vector<int>> adj(p.size(), vector<int>(p.size(), 0));
vector<vector<size_t>> roots(p.size());
vector<bool> visited(p.size(), 0);
for (size_t i = 0; i < p.size(); i++)
if (!visited[i])
{
visited[i] = 1;
roots[connected.repr(i)].push_back(i);
for (size_t j = 0; j < p.size(); j++)
if (j != i && one_connected.same_set(i, j))
{
adj[i][j] = adj[j][i] = 1;
visited[j] = 1;
}
}
for (auto const &v : roots)
{
if (v.size() > 1)
for (size_t i = 0; i < v.size(); i++)
adj[v[i]][v[(i + 1) % v.size()]] = adj[v[(i + 1) % v.size()]][v[i]] = 1;
if (v.size() == 2)
return 0;
}
build(adj);
return 1;
}
