#include "supertrees.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;
using ll = long long;
struct UnionFind
{
vector<int> id;
UnionFind() {}
UnionFind(int N)
{
id.assign(N, -1);
}
int find(int u)
{
if (id[u] < 0) return u;
return id[u] = find(id[u]);
}
bool merge(int u, int v)
{
u = find(u), v = find(v);
if (u == v) return false;
if (id[u] > id[v]) swap(u, v);
id[u] += id[v];
id[v] = u;
return true;
}
vector<vector<int>> getComps()
{
vector<vector<int>> ret;
vector<vector<int>> comps(SZ(id));
for (int i(0); i < SZ(id); ++i)
comps[find(i)].push_back(i);
for (auto v : comps)
if (SZ(v))
ret.push_back(v);
return ret;
}
};
int construct(vector<vector<int>> p)
{
int nbSommets = SZ(p);
vector<vector<int>> sol(nbSommets, vector<int>(nbSommets));
UnionFind uf(nbSommets);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (p[i][j] == 3)
return 0;
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (p[i][j] == 1)
uf.merge(i,j);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (uf.find(i) == uf.find(j) and p[i][j] != 1)
return 0;
for (int i(0); i< nbSommets; ++i)
if (uf.find(i) != i)
sol[uf.find(i)][i] = sol[i][uf.find(i)] = 1;
UnionFind uf2(nbSommets);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (p[i][j])
uf2.merge(i, j);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (uf2.find(i) == uf2.find(j) and uf.find(i) != uf.find(j) and p[i][j] != 2)
return 0;
auto comps = uf2.getComps();
for (auto v : comps)
{
vector<int> roots;
for (auto u : v)
if (uf.find(u) == u)
roots.push_back(u);
if (SZ(roots) == 1) continue;
bool aTwo(false);
for (auto u : v)
for (auto w : v)
if (p[u][w] == 2)
aTwo = true;
if (aTwo and SZ(roots) <= 2)
return 0;
roots.push_back(roots.front());
for (int i(1); i < SZ(roots); ++i)
sol[roots[i-1]][roots[i]] = sol[roots[i]][roots[i-1]] = true;
}
build(sol);
return 1;
}
