#include "supertrees.h"
#include <iostream>
#include <vector>
using namespace std;
#define add push_back
#define len(a) ((int)(a).size())
int construct(vector<vector<int>> p) {
vector<vector<int>> answer(len(p));
vector<int> h(len(p)), s(len(p));
vector<int> v[1005];
int now = 0;
for(int i = 0; i < len(p); i++){
answer[i].resize(len(p));
for(int j = 0; j < i; j++){
if(p[i][j] != 0){
h[i] = h[j];
break;
}
}
if(h[i] == 0){
h[i] = ++now;
}
v[h[i]].add(i);
}
for(int i = 0; i < len(p); i++){
for(int j = 0; j < len(p); j++){
if(i == j) continue;
if(p[i][j] != 0 && h[i] != h[j]){
// cout << "E1.1" << endl;
return 0;
}
if(p[i][j] == 0 && h[i] == h[j]){
// cout << "E1.2" << endl;
return 0;
}
}
}
// for(int i = 1; i <= now; i++){
// for(int j = 0; j < len(v[i]); j++){
// cout << v[i][j] << " ";
// }
// cout << endl;
// }
vector<vector<int>> a;
int x, v1, v2;
a.resize(1005);
for(int i = 1; i <= now; i++){
x = 0;
for(int j = 0; j < len(v[i]); j++){
v1 = v[i][j];
for(int k = 0; k < j; k++){
v2 = v[i][k];
if(p[v1][v2] == 1){
s[v1] = s[v2];
break;
}
}
if(s[v1] == 0){
s[v1] = ++x;
}
a[s[v1]].add(v1);
}
if(x == 2) return 0;
for(int j = 0; j < len(v[i]); j++){
v1 = v[i][j];
for(int k = 0; k < len(v[i]); k++){
if(j == k) continue;
v2 = v[i][k];
if(p[v1][v2] != 1 && s[v1] == s[v2]){
// cout << "E2.1" << endl;
return 0;
}
if(p[v1][v2] == 1 && s[v1] != s[v2]){
// cout << "E2.2" << endl << "----------" << endl << v1 << " " << v2 << " : " << s[v1] << " " << s[v2] << endl;
return 0;
}
}
}
for(int j = 1; j <= x; j++){
for(int k = 1; k < len(a[j]); k++){
answer[a[j][k - 1]][a[j][k]] = answer[a[j][k]][a[j][k - 1]] = 1;
}
if(x > 1){
if(j == 1) answer[a[j][0]][a[x][0]] = answer[a[x][0]][a[j][0]] = 1;
else answer[a[j][0]][a[j - 1][0]] = answer[a[j - 1][0]][a[j][0]] = 1;
}
}
for(int j = 1; j <= x; j++) a[j].clear();
}
build(answer);
return 1;
}
