#include "supertrees.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
struct DSU {
int n;
vector<int> dad;
vector<vector<int>> t;
DSU(int n_) : n(n_), dad(n, -1), t(n) {
for (int i = 0; i < n; ++i) {
t[i] = {i};
}
}
int Find(int x) {
if (dad[x] == -1) return x;
return dad[x] = Find(dad[x]);
}
bool Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return false;
if (t[x].size() < t[y].size()) swap(x, y);
t[x].insert(t[x].end(), t[y].begin(), t[y].end());
dad[y] = x;
return true;
}
bool Connected(int x, int y) {
return Find(x) == Find(y);
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n));
auto AddEdge = [&](int a, int b) {
if (a != b) ans[a][b] = ans[b][a] = 1;
};
DSU dsu(n);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i][j] == 1) {
if (dsu.Union(i, j)) {
AddEdge(i, j);
}
}
}
}
vector<int> roots;
for (int i = 0; i < n; ++i) {
if (dsu.Find(i) == i) roots.emplace_back(i);
}
for (int node : roots) {
for (int i = 0; i < (int)dsu.t[node].size(); ++i) {
int x = dsu.t[node][i];
for (int j = i + 1; j < (int)dsu.t[node].size(); ++j) {
int y = dsu.t[node][j];
if (p[x][y] != 1) return 0;
}
}
}
DSU dsu_roots(n);
for (int i = 0; i < (int)roots.size(); ++i) {
int x = roots[i];
for (int j = i + 1; j < (int)roots.size(); ++j) {
int y = roots[j];
if (p[x][y] == 2) {
dsu_roots.Union(x, y);
}
}
}
for (int root : roots) {
if (dsu_roots.Find(root) != root) continue;
auto &v = dsu_roots.t[root];
for (int i = 0; i < (int)v.size(); ++i) {
int j = i + 1;
if (j == (int)v.size()) j = 0;
AddEdge(v[i], v[j]);
}
}
bool ret = true;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (dsu.Connected(i, j)) {
ret &= p[i][j] == 1;
} else {
ret &= p[i][j] != 1;
}
if (dsu.Find(i) != dsu.Find(j) &&
dsu_roots.Connected(dsu.Find(i), dsu.Find(j))) {
ret &= p[i][j] == 2;
} else {
ret &= p[i][j] != 2;
}
}
}
if (!ret) return 0;
build(ans);
return 1;
}
