#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector < bool > u(n);
vector < int > now;
vector < vector < int > > all;
int cur;
for (int i = 0; i < n; ++i) {
if (u[i]) {
continue;
}
now.clear();
for (int j = i; j < n; ++j) {
if (u[j] || p[i][j] != 1) {
continue;
}
now.push_back(j);
u[j] = 1;
}
for (auto v : now) {
for (auto u : now) {
if (p[v][u] != 1) {
return 0;
}
}
}
for (int j = 1; j < (int)(now.size()); ++j) {
answer[now[j - 1]][now[j]] = 1;
answer[now[j]][now[j - 1]] = 1;
}
all.push_back(now);
}
for (int i = 0; i < (int)(all.size()); ++i) {
for (int j = i + 1; j < (int)(all.size()); ++j) {
for (auto v : all[i]) {
for (auto u : all[j]) {
if (p[v][u] != p[all[i][0]][all[j][0]]) {
return 0;
}
}
}
}
}
int last;
for (int i = 0; i < n; ++i) {
u[i] = 0;
}
vector < int > c(n);
int it = 0;
for (int i = 0; i < (int)(all.size()); ++i) {
if (u[i]) {
continue;
}
cur = 1;
last = all[i].back();
now.clear();
for (auto j : all[i]) {
now.push_back(j);
}
for (int j = i + 1; j < (int)(all.size()); ++j) {
if (!u[j] && p[last][all[j].back()] == 2) {
answer[last][all[j].back()] = 1;
answer[all[j].back()][last] = 1;
last = all[j].back();
u[j] = 1;
++cur;
for (auto k : all[j]) {
now.push_back(k);
}
}
}
if (cur == 2) {
return 0;
}
++it;
for (auto u : now) {
c[u] = it;
for (auto v : now) {
if (u != v) {
return 0;
}
}
}
for (auto u : now) {
for (int j = 0; j < n; ++j) {
if (c[j] != it && p[u][j]) {
return 0;
}
}
}
if (last != all[i].back()) {
answer[last][all[i].back()] = 1;
answer[all[i].back()][last] = 1;
}
}
build(answer);
return 1;
}
