#include "supertrees.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
constexpr int maxn = 1e3 + 5;
int next_group = 1;
int groups[maxn] = { 0 }, gnode[maxn] = { 0 }, siz[maxn] = { 0 };
bool done[maxn] = { 0 };
vector <int> adj[maxn];
int construct(std::vector<std::vector<int>> p) {
int g;
int n = p.size();
vector<vector<int>> output(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
if (groups[i]) continue;
g = next_group++;
vector<int> clique = { i };
for (int y = i + 1; y < n; y++)
{
if (p[i][y] == 1) clique.emplace_back(y);
}
gnode[g] = i;
for (int y : clique) {
groups[y] = g;
if (p[y] != p[gnode[g]]) goto impossible;
}
for (int i = 1; i < (int)clique.size(); i++)
{
output[clique[i]][clique[i - 1]] = output[clique[i - 1]][clique[i]] = 1;
}
siz[g] = clique.size();
set <int> seen;
for (int y = 0; y < i; y++)
{
if (p[i][y] != 0 && seen.count(groups[y]) == 0) {
adj[g].push_back(groups[y]);
seen.insert(groups[y]);
adj[groups[y]].push_back(g);
}
}
}
// cerr << "Groups complete\n";
// Combining groups
// in each connected component, there must be either 2, 3, or none, but not both
for (int i = 1; i < next_group; i++)
{
if (done[i]) continue;
vector<int> gs = adj[i];
gs.push_back(i);
vector<int> twos, threes, ones;
if (gs.size() == 1) continue;
// cout << i << "\n";
// for (int y : gs) cout << y << " ";
// cout << "\n";
for (int x : gs)
{
done[x] = true;
int one = 0;
bool two, three;
two = three = false;
for (int y : p[gnode[x]])
{
if (y == 1) one ++;
else if (y == 2) two = true;
else if (y == 3) three = true;
}
if (two && three) goto impossible;
if (one > 1) ones.emplace_back(x);
else if (two) twos.emplace_back(x);
else if (three) threes.emplace_back(x);
}
// cout << "Counting finished\n";
// cerr << ones.size() << " " << twos.size() << " " << threes.size() << " \n";
if (threes.empty())
{
// Twos
if (gs.size() == 2) goto impossible;
// Make a cycle
for (int y = 0; y < (int)gs.size() - 1; y++)
{
output[gnode[gs[y]]][gnode[gs[y + 1]]] = output[gnode[gs[y + 1]]][gnode[gs[y]]] = 1;
}
output[gnode[gs[0]]][gnode[gs[gs.size() - 1]]] = output[gnode[gs[gs.size() - 1]]][gnode[gs[0]]] = 1;
}
}
// Build
build(output);
return 1;
impossible:
return 0;
}
