#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int par[N];
int fp(int x) {
if (par[x] == -1) return x;
return par[x] = fp(par[x]);
}
int construct(std::vector<std::vector<int>> p) {
memset(par, -1, sizeof(par));
int n = p.size();
vector<int> id(n, -1);
vector<bool> vis(n, false);
vector<vector<int>> b(n, vector<int> (n, 0));
for (int i = 0; i < n; i++) {
if (p[i][i] == 0) return 0;
for (int j = 0; j < n; j++) {
if (p[i][j] != p[j][i]) return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!p[i][j] || i == j) continue;
int u = fp(i), v = fp(j);
if (u == v) continue;
par[u] = v;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (fp(i) == fp(j) && !p[i][j]) return 0;
}
}
int cnt = 0;
vector<vector<int>> ch(n);
for (int i = 0; i < n; i++) ch[fp(i)].emplace_back(i);
for (int i = 0; i < n; i++) {
if (ch[i].empty()) continue;
int m = ch[i].size();
bool is2 = false, is3 = false;
for (auto &u : ch[i]) {
for (auto &v : ch[i]) {
if (u == v) continue;
if (p[u][v] == 2) is2 = true;
if (p[u][v] == 3) is3 = true;
}
}
if (is3) return 0;
if (!is2) {
for (int j = 1; j < m; j++) {
int x = ch[i][j], y = ch[i][j-1];
b[x][y] = b[y][x] = 1;
}
} else {
vector<vector<int>> l;
for (auto &u : ch[i]) {
if (vis[u]) continue;
vector<int> t;
for (auto &v : ch[i]) {
if (p[u][v] == 1) {
if (vis[v]) return 0;
t.emplace_back(v), vis[v] = true;
}
}
l.emplace_back(t);
}
for (auto &t : l) {
for (auto &u : t) {
id[u] = cnt;
for (auto &v : t) {
if (p[u][v] != 1) return 0;
}
}
cnt++;
}
for (auto &u : ch[i]) {
for (auto &v : ch[i]) {
if (id[u] == id[v]) continue;
if (p[u][v] == 1) return 0;
}
}
for (auto &t : l) {
int k = t.size();
for (int j = 1; j < k; j++) {
int x = t[j], y = t[j-1];
b[x][y] = b[y][x] = 1;
}
}
vector<int> s;
for (auto &t : l) s.emplace_back(t[0]);
int k = s.size();
if (k < 3) return 0;
for (int j = 1; j <= k; j++) {
int x = s[j%k], y = s[j-1];
b[x][y] = b[y][x] = 1;
}
}
}
build(b);
return 1;
}
