#include <vector>
#include <iostream>
#include "supertrees.h"
using namespace std;
int n;
int const NMAX = 1000;
int comp[3][NMAX];
int path[NMAX][NMAX];
int last[1 + NMAX];
int cleng[1 + NMAX];
void buildComp(int special, int node, int rep) {
//cerr << special << ' ' << node << ' ' << rep << '\n';
if(comp[special][node] == -1) {
comp[special][node] = rep;
for(int i = 0;i < n;i++) {
if(path[node][i] != 0 && path[node][i] <= special) {
buildComp(special, i, rep);
}
}
}
}
bool computeIsGood() {
for(int i = 0;i < n;i++) {
for(int j = i+1;j < n;j++) {
if(comp[1][i] == comp[1][j] && path[i][j] != 1) {
//cerr << "r1 " << i << ' ' << j << ' ' << path[i][j] << '\n';
return false;
} else if(comp[2][i] == comp[2][j] && path[i][j] == 0) {
//cerr << "r2 " << i << ' ' << j << ' ' << path[i][j] << '\n';
return false;
}
}
}
return true;
}
int construct(vector<vector<int>> p) {
n = p.size();
vector<vector<int>> sol;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
sol.push_back(row);
}
//cerr << "done creation of sol\n";
for(int i = 0;i < n;i++) {
comp[1][i] = comp[2][i] = -1;
last[i] = -1;
}
for(int i = 0;i < n;i++) {
if(p[i][i] != 1) {
return 0;
}
for(int j = 0;j < n;j++) {
path[i][j] = p[i][j];
if(p[i][j] == 3 || p[i][j] != p[j][i]) {
return 0;
}
}
}
//cerr << "done creation of path\n";
//cerr << "first buildComp\n ";
for(int i = 0;i < n;i++) {
buildComp(1, i, i);
//cerr << comp[1][i] << ' ';
}
//cerr << '\n';
//cerr << "second buildComp\n ";
for(int i = 0;i < n;i++) {
buildComp(2, i, i);
//cerr << comp[2][i] << ' ';
}
//cerr << '\n';
bool isGood = computeIsGood();
if(!isGood) {
return 0;
}
// build chains
for(int i = 0;i < n;i++) {
if(last[comp[1][i]] != -1) {
int temp = last[comp[1][i]];
sol[i][temp] = sol[temp][i] = 1;
}
last[comp[1][i]] = i;
}
//cerr << "built chains\n";
// reset last
for(int i = 0;i < n;i++) {
last[i] = -1;
}
// build cycles
for(int i = 0;i < n;i++) {
if(comp[1][i] == i) {
if(last[comp[2][i]] != -1) {
int temp = last[comp[2][i]];
sol[i][temp] = sol[temp][i] = 1;
cleng[comp[2][i]]++;
}
last[comp[2][i]] = i;
}
}
for(int i = 0;i < n;i++) {
if(comp[1][i] == i) {
if(comp[2][i] == i && last[i] != i) {
sol[i][last[i]] = sol[last[i]][i] = 1;
cleng[comp[2][i]]++;
}
}
}
for(int i = 0;i < n;i++) {
if(comp[1][i] == i && comp[2][i] == i) {
if(cleng[comp[2][i]] == 2 || cleng[comp[2][i]] == 1) {
return false;
}
}
}
//cerr << "built cycles\n";
build(sol);
return 1;
}
