#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " " << a << endl
#define nl "\n"
lli n,ult,a,b,c,d;
lli padre[1002],grupo[1002],visitados[1002],inicios[1002],finales[1002],cant[1002];
bool res;
vector<lli> cabezas;
void procesa(lli act) {
if (padre[act] != act) {
procesa(padre[act]);
padre[act] = ult;
}
else ult = act;
}
void calcula(lli act) {
if (grupo[act] != act) {
calcula(grupo[act]);
grupo[act] = ult;
}
else ult = act;
}
int construct(std::vector<std::vector<int>> p) {
res = true;
n = p.size();
vector<vector<int> > puentes(n, vector<int> (n, 0));
rep(i,0,n-1) padre[i] = i;
rep(i,0,n-1) grupo[i] = i;
rep(i,0,n-1) {
rep(j,i,n-1){
if (visitados[j] == 1) continue;
if (i == j) continue;
if (p[i][j] != p[j][i]) res = false;
if (p[i][j] == 3) res = false;
if (res == false) return 0;
if (p[i][j] == 1) {
padre[j] = i;
puentes[i][j] = 1;
puentes[j][i] = 1;
visitados[j] = 1;
}
}
}
rep(i,0,n-1) {
if (padre[i] != i) continue;
rep(j,i,n-1){
if (i == j) continue;
if (padre[i] != i) continue;
if (visitados[j] == 2) continue;
if (p[i][j] == 2) {
grupo[j] = i;
visitados[j]=2;
}
}
}
rep(i,0,n-1) {
rep(j,i,n-1) {
if(i == j) continue;
procesa(i);
a = ult;
procesa(j);
b = ult;
calcula(a);
c = ult;
calcula(b);
d = ult;
if (p[i][j] == 0){
if (a != b && c != d) continue;
else res = false;
}
else if (p[i][j] == 1){
if (a == b && c == d) continue;
else res = false;
}
else {
if (a != b && c == d) continue;
else res = false;
}
if (!res) return 0;
}
}
rep(i,0,n-1) {
if (padre[i] == i) {
calcula(i);
if (cant[ult] == 0) {
inicios[ult] = i;
finales[ult] = i;
cant[ult] = 1;
}
else {
puentes[i][finales[ult]] = 1;
puentes[finales[ult]][i] = 1;
//cout << ult << ' ' << finales[ult] << endl;
finales[ult] = i;
cant[ult]++;
}
}
}
rep(i,0,n-1) {
if (cant[i] == 2) return 0;
if (cant[i] > 2) {
puentes[finales[i]][inicios[i]] = 1;
puentes[inicios[i]][finales[i]] = 1;
}
}
build(puentes);
return 1;
}
