#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct DSU {
vector<int> rank, parent;
DSU(int n) {
rank.assign(n, 1);
parent.resize(n);
for (int i=0; i<n; i++) {
parent[i] = i;
}
}
int find(int n) {
return (n == parent[n] ? n : parent[n] = find(parent[n]));
}
void unite(int n1, int n2) {
int p1 = find(n1);
int p2 = find(n2);
rank[p1] += rank[p2];
parent[p2] = p1;
}
};
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n, 0));
bool can = true;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] != p[j][i]) can = false;
}
}
if (!can) {
return 0;
}
DSU dsu1(n);
DSU dsu2(n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (p[i][j] == 1) dsu1.unite(i, j);
if (p[i][j] == 2) dsu2.unite(i, j);
}
}
//Unir 1-componente
for (int i=0; i<n; i++) {
int pi = dsu1.find(i);
if (pi==i) {
vector<int> cmp = {i};
for (int j=0; j<n; j++) {
if (j==i) continue;
int pj = dsu1.find(j);
if (pj == i) {
cmp.push_back(j);
}
}
for (auto x : cmp) {
ans[i][x] = ans[x][i] = 1;
}
for (auto j1 : cmp) {
for (auto j2 : cmp) {
if (p[j1][j2] == p[j2][j1] && p[j1][j2] == 0) {
return 0;
}
}
}
}
}
//Unir 2-componentes
for (int i=0; i<n; i++) {
int pi = dsu2.find(i);
if (pi==i) {
vector<int> cmp = {i};
for (int j=0; j<n; j++) {
if (j==i) continue;
int pj = dsu2.find(j);
if (pj == i) {
cmp.push_back(j);
}
}
int m = cmp.size();
vector<bool> vis(m, false);
int u = cmp[0];
for (auto x : cmp) {
for (auto y : cmp) {
if (x == y) continue;
if (p[x][y] == 1) {
u = x;
vis[x] = vis[y] = true;
}
}
}
set<int> s;
for (auto x : cmp) {
if (!vis[x]) {
s.insert(x);
}
}
s.insert(u);
vector<int> a(s.begin(), s.end());
m = a.size();
for (int j=0; j<m; j++) {
int u = a[j];
int v = a[(j+1)%m];
ans[u][v] = ans[v][u] = 1;
}
for (auto x : cmp) {
for (auto y : cmp) {
if (p[x][y] == 0) return 0;
}
}
if (cmp.size()==2) return 0;
}
}
for (int i=0; i<n; i++) {
ans[i][i] = 0;
}
build(ans);
return 1;
}
