#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<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;
}
}
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 (is2 && is3) return 0;
if (!is2 && !is3) {
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<int> l1, l2;
for (auto &u : ch[i]) {
bool in = true;
for (auto &v : ch[i]) {
if (u == v) continue;
if (p[u][v] < 2) in = false;
}
if (!in) l1.emplace_back(u);
else l2.emplace_back(u);
}
for (auto &u : l1) {
for (auto &v : l1) {
if (u == v) continue;
if (p[u][v] != 1) return 0;
}
}
for (auto &u : l2) {
for (auto &v : ch[i]) {
if (u == v) continue;
if (p[u][v] != 3 && is3) return 0;
if (p[u][v] != 2 && is2) return 0;
}
}
int s1 = l1.size(), s2 = l2.size();
if (is3 && s2 < 3) return 0;
if (is2 && s2 < 2) return 0;
for (int j = 1; j < s1; j++) {
int x = l1[j], y = l1[j-1];
b[x][y] = b[y][x] = 1;
}
for (int j = 1; j <= s2; j++) {
int x = l2[j%s2], y = l2[j-1];
b[x][y] = b[y][x] = 1;
}
if (l1.empty()) {
if (is3 && s2 < 4) return 0;
if (is2 && s2 < 3) return 0;
if (is3) b[l2[0]][l2[2]] = b[l2[2]][l2[0]] = 1;
} else {
int x = l1[0];
b[x][l2[0]] = b[l2[0]][x] = 1;
b[x][l2.back()] = b[x][l2.back()] = 1;
if (is3) b[x][l2[1]] = b[l2[1]][x] = 1;
}
}
}
build(b);
return 1;
}
