#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
ll V;
vc<vc<ll>> a;
vc<vc<ll>> cms;
vc<ll> cid;
vc<vc<ll>> ans;
bool divide() {
cms.pub({0});
cid.resize(V);
cid[0] = 0;
for (ll i = 1; i < V; i++) {
ll id = -1;
for (ll j = 0; j < i; j++) {
if (a[i][j] == 0)
continue;
if (id != -1 and cid[j] != id)
return false;
id = cid[j];
}
if (id == -1) {
cid[i] = sz(cms);
cms.pub({i});
} else {
cid[i] = id;
cms[id].pub(i);
}
}
return true;
}
bool make(vc<ll> &com) {
vc<vc<ll>> dms;
vc<ll> did(V, 0);
dms.pub({com[0]});
did[com[0]] = 0;
for (ll i = 1; i < sz(com); i++) {
ll v = com[i];
ll cnt = 0;
ll id = -1;
for (ll j = 0; j < i; j++) {
ll w = com[j];
if (a[v][w] == 2)
continue;
if (id != -1 and did[w] != id)
return false;
id = did[w];
cnt++;
}
if (id == -1) {
did[v] = sz(dms);
dms.pub({v});
} else {
if (cnt < sz(dms[id]))
return false;
did[v] = id;
dms[id].pub(v);
}
}
for (auto &dom : dms) {
for (ll i = 0; i + 1 < sz(dom); i++)
ans[dom[i]][dom[i + 1]] = 1;
}
if (sz(dms) == 1)
return true;
if (sz(dms) == 2)
return false;
for (ll i = 0; i + 1 < sz(dms); i++)
ans[dms[i][0]][dms[i + 1][0]] = 1;
ans[dms[sz(dms) - 1][0]][dms[0][0]] = 1;
return true;
}
void fix() {
for (ll i = 0; i < V; i++)
for (ll j = 0; j < V; j++)
ans[i][j] = ans[j][i] = max(ans[i][j], ans[j][i]);
}
ll construct(vc<vc<ll>> p) {
a = p;
V = sz(a);
for (ll i = 0; i < V; i++)
for (ll j = 0; j < V; j++)
if (a[i][j] == 3)
return 0;
if (not divide())
return 0;
ans.assign(V, vc<ll>(V, 0));
for (auto &com : cms)
if (not make(com))
return 0;
fix();
build(ans);
return 1;
}
