#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1032;
vector <int> g1[N], g2[N];
int r1[N], r2[N];
bool vis[N];
vector <int> v[N];
void dfs1 (int v) {
vis[v] = true;
for (int u : g1[v]) {
if (!vis[u]) {
r1[u] = r1[v];
dfs1 (u);
}
}
}
void dfs2 (int v) {
vis[v] = true;
for (int u : g2[v]) {
if (!vis[u]) {
r2[u] = r2[v];
dfs2 (u);
}
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> ans;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
ans.push_back(row);
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 1) {
g1[i].push_back(j);
g1[j].push_back(i);
}
if (p[i][j] >= 1) {
g2[i].push_back(j);
g2[j].push_back(i);
}
}
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
r1[i] = i;
dfs1(i);
}
}
for (int i = 0; i < n; i++)
vis[i] = false;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
r2[i] = i;
dfs2(i);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int w;
if (r2[i] != r2[j]) {
w = 0;
} else if (r1[i] == r1[j]) {
w = 1;
} else {
w = 2;
}
if (p[i][j] != w)
return 0;
}
}
for (int i = 0; i < n; i++) {
if (r1[i] != i) {
ans[i][r1[i]] = 1;
ans[r1[i]][i] = 1;
} else {
v[r2[i]].push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (v[i].size() == 2)
return 0;
if (v[i].size() <= 1)
continue;
int sz = (int)v[i].size();
for (int j = 0; j < sz; j++) {
ans[v[i][j]][v[i][(j + 1) % sz]] = true;
ans[v[i][(j + 1) % sz]][v[i][j]] = true;
}
}
build(ans);
return 1;
}
