#include "supertrees.h"
#include <vector>
#include <queue>
#include <set>
using namespace std;
struct DSU {
vector<int> par, sz;
DSU(int n) : par(n), sz(n) {
for (int i=0; i<n; i++) {
par[i] = i;
sz[i] = 1;
}
}
int findRoot(int u) {
if (par[u] != u)
par[u] = findRoot(par[u]);
return par[u];
}
bool unite(int u, int v) {
u = findRoot(u), v = findRoot(v);
if (u == v)
return false;
if (sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
return true;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector<vector<int>> adj(n);
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) {
if (p[i][j] == 3)
return 0;
if (p[i][j] == 1)
adj[i].push_back(j);
}
vector<int> id(n, -1);
vector<vector<int>> comp;
queue<int> q;
for (int i=0; i<n; i++)
if (id[i] == -1) {
comp.emplace_back();
q.push(i);
id[i] = (int) comp.size() - 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : comp.back())
if (p[u][v] != 1)
return 0;
comp.back().push_back(u);
for (int v : adj[u])
if (id[v] == -1) {
q.push(v);
id[v] = (int) comp.size() - 1;
}
}
}
int m = comp.size();
DSU ds(m);
vector<vector<bool>> two(m, vector<bool>(m));
for (int i=0; i<m; i++) {
for (int j=1; j<(int)comp[i].size(); j++)
answer[comp[i][j-1]][comp[i][j]] = answer[comp[i][j]][comp[i][j-1]] = 1;
for (int u : comp[i])
for (int v=0; v<n; v++)
if (p[u][v] == 2) {
two[id[u]][id[v]] = two[id[v]][id[u]] = true;
ds.unite(id[u], id[v]);
}
}
vector<vector<int>> big(m);
for (int i=0; i<m; i++) {
for (int v : big[ds.par[i]])
if (!two[i][v])
return 0;
big[ds.par[i]].push_back(i);
}
auto get = [&] (int id) {
return comp[id][0];
};
for (auto &c : big) {
if (c.size() == 2)
return 0;
for (int i=1; i<(int)c.size(); i++)
answer[get(c[i-1])][get(c[i])] = answer[get(c[i])][get(c[i-1])] = 1;
if (c.size() > 2)
answer[get(c.back())][get(c[0])] = answer[get(c[0])][get(c.back())] = 1;
}
build(answer);
return 1;
}
