#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
public:
vector<int> p;
DisjointSet() {}
DisjointSet(int sz) : p(sz) {
iota(begin(p), end(p), 0);
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
int Unite(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) {
return 0;
}
p[x] = y;
return 1;
}
bool SameSet(int x, int y) {
return Find(x) == Find(y);
}
bool IsRoot(int x) {
return Find(x) == x;
}
};
int construct(vector<vector<int>> p) {
int n = (int) p.size();
vector<vector<int>> ans(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) {
return 0;
}
}
}
DisjointSet D(n), T(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] > 0) {
D.Unite(i, j);
}
}
}
vector<vector<int>> comps(n);
vector<vector<int>> trees(n);
for (int i = 0; i < n; i++) {
comps[D.Find(i)].emplace_back(i);
}
for (const auto &c : comps) {
if (c.empty()) {
continue;
}
for (auto i : c) {
for (auto j : c) {
if (p[i][j] == 0) {
return 0;
}
}
}
for (auto i : c) {
for (auto j : c) {
if (p[i][j] == 1) {
T.Unite(i, j);
}
}
}
for (auto i : c) {
trees[T.Find(i)].emplace_back(i);
}
vector<int> roots;
for (auto r : c) {
if (T.IsRoot(r)) {
roots.emplace_back(r);
for (auto i : trees[r]) {
for (auto j : trees[r]) {
if (p[i][j] == 2) {
return 0;
}
}
}
for (int i = 0; i + 1 < (int) trees[r].size(); i++) {
ans[trees[r][i]][trees[r][i + 1]] = 1;
ans[trees[r][i + 1]][trees[r][i]] = 1;
}
}
}
if (roots.size() == 1) {
continue;
}
if (roots.size() == 2) {
return 0;
}
roots.emplace_back(roots.front());
for (int i = 0; i + 1 < (int) roots.size(); i++) {
ans[roots[i]][roots[i + 1]] = 1;
ans[roots[i + 1]][roots[i]] = 1;
}
}
build(ans);
return 1;
}
