#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[2][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] == 2 && seen.count(groups[y]) == 0) {
adj[0][g].push_back(groups[y]);
seen.insert(groups[y]);
adj[0][groups[y]].push_back(g);
}
if (p[i][y] == 3 && seen.count(groups[y]) == 0) {
adj[1][g].push_back(groups[y]);
seen.insert(groups[y]);
adj[1][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;
if (!adj[0][i].empty() && !adj[1][1].empty()) goto impossible;
int t;
if (!adj[0][i].empty()) t = 0;
else t = 1;
vector<int> gs = adj[t][i];
gs.insert(gs.begin(), i);
vector<int> twos, threes;
if (gs.size() == 1) continue;
if (gs.size() == 2) goto impossible;
// cout << i << "\n";
// for (int y : gs) cout << y << " ";
// cout << "\n";
for (int x : gs)
{
vector<int> test = adj[t][x];
if (!adj[t ^ 1][x].empty()) goto impossible;
test.insert(lower_bound(test.begin(), test.end(), x), x);
if (test != gs) goto impossible;
done[x] = true;
}
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;
if (t == 0)
{
if (gs.size() < 3) goto impossible;
}
else
{
if (gs.size() < 4) goto impossible;
output[gnode[gs[0]]][gnode[gs[2]]] = output[gnode[gs[2]]][gnode[gs[0]]] = 1;
}
}
// Build
build(output);
return 1;
impossible:
return 0;
}
