#include "supertrees.h"
#include <vector>
#include <cassert>
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer(n, std::vector<int>(n, 0));
std::vector<bool> wtf(n, false);
for(int r = 0; r < n; r++) {
if(wtf[r]) continue;
std::vector<std::vector<int>> chains;
std::vector<int> others;
int lul = 2;
for(int j = 0; j < n; j++) {
if(p[r][j]) {
if(wtf[j]) {
return 0;
}
int x = 0;
while(x < (int) chains.size() && p[j][chains[x][0]] != 1) {
x++;
}
if(x == (int) chains.size()) {
chains.emplace_back(0, 0);
}
chains[x].push_back(j);
wtf[j] = true;
} else {
others.push_back(j);
}
}
int m = (int) chains.size();
for(int i = 0; i < m; i++) {
for(int j = 0; j < m; j++) {
for(auto v1 : chains[i]) for(auto v2 : chains[j]) {
lul = std::max(lul, p[v1][v2]);
}
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < m; j++) {
for(auto v1 : chains[i]) for(auto v2 : chains[j]) {
int want = i == j ? 1 : lul;
if(p[v1][v2] != want) {
return 0;
}
}
}
for(auto v1 : chains[i]) {
for(auto o : others) {
if(p[v1][o] || p[o][v1]) {
return 0;
}
}
}
}
if(m == 1) {
int last = -1;
for(auto v : chains[0]) {
if(last != -1) {
answer[last][v] = answer[v][last] = 1;
}
last = v;
}
} else if(m == 2) {
return 0;
} else if(m != 4 && lul == 3) {
return 0;
} else {
assert(m > 2);
for(int i = 0; i < m; i++) {
int u = chains[i][0], v = chains[(i+1)%m][0];
answer[u][v] = answer[v][u] = 1;
}
if(lul == 3) {
int u = chains[0][0], v = chains[2][0];
answer[u][v] = answer[v][u] = 1;
}
for(auto chain : chains) {
int last = -1;
for(auto v : chain) {
if(last != -1) {
answer[last][v] = answer[v][last] = 1;
}
last = v;
}
}
}
}
build(answer);
return 1;
}
