#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) {
for (int j = 0; j < n; ++j) {
if (p[i][j] == 3) return 0;
}
}
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
vector<bool> vis(n);
vector<int> lidx(n), cidx(n);
for (int it = 0; it < n; ++it) {
if (vis[it]) continue;
queue<int> comp;
vector<int> cycle;
comp.push(it);
while (comp.size()) {
int x = comp.front();
comp.pop();
if (vis[x]) continue;
vector<int> curr_line;
cycle.push_back(x);
queue<int> qline;
qline.push(x);
while (qline.size()) {
int y = qline.front();
qline.pop();
if (vis[y]) continue;
vis[y] = 1;
curr_line.push_back(y);
cidx[y] = it;
lidx[y] = x;
for (int j = 0; j < n; ++j) {
if (p[y][j] == 2) {
comp.push(j);
} else if (p[y][j] == 1) {
qline.push(j);
}
}
}
if (curr_line.size() > 1) {
for (int i = 0; i < (int)curr_line.size() - 1; ++i) {
int a = curr_line[i];
int b = curr_line[i + 1];
answer[a][b] = answer[b][a] = 1;
}
}
}
if (cycle.size() == 2) return 0;
if (cycle.size() == 1) continue;
for (int i = 0; i < (int)cycle.size(); ++i) {
int a = cycle[i];
int b = cycle[(i + 1) % cycle.size()];
answer[a][b] = answer[b][a] = 1;
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (lidx[i] == lidx[j]) {
if (p[i][j] != 1) return 0;
} else if (cidx[i] == cidx[j]) {
if (p[i][j] != 2) return 0;
} else {
if (p[i][j] != 0) return 0;
}
}
}
build(answer);
return 1;
}
