#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define debugsl(y) cout << #y << " = " << y << ", "
#define debug(x) debugsl(x) << endl
#define MAX_N 1001
vector<vector<int> > respuesta, entrada;
vector<int> linea[MAX_N]; // VECTOR PARA GUARDAR LOS NODOS DE CADA LINEA
vector<int> ciclo[MAX_N]; // NODOS EN CADA CICLO
int grupo[MAX_N], grupoCiclo[MAX_N], cicloGrupos[MAX_N][MAX_N]; // SUBGRAFO AL QUE PERTENECE CADA NODO
void puente(int a, int b){
if (a == b) return;
respuesta[a][b] = 1;
respuesta[b][a] = 1;
}
bool checaGrupos(int a, int b){
bool ok = true;
if (cicloGrupos[a][b] == 1 || a == b) return true;
for(auto i : linea[a]){
for(auto j : linea[b]){
if (entrada[i][j] != 2) {
ok = false;
break;
}
}
if (!ok) break;
}
if (ok){
cicloGrupos[a][b] = 1;
cicloGrupos[b][a] = 1;
}
return ok;
}
int construct(std::vector<std::vector<int> > p) {
int n = p.size();
entrada = p;
rep(i, 0, n - 1){
vector<int> fila;
fila.resize(n);
respuesta.push_back(fila);
}
rep(i, 0, n - 1) grupo[i] = grupoCiclo[i] = i;
rep(i, 0, n - 1){
rep(j, i + 1, n - 1){
if (p[i][j] == 0 && grupo[i] == grupo[j]) return 0;
else if(p[i][j] == 1 && grupo[i] == i && grupo[j] == j){
linea[i].push_back(j);
grupo[j] = i;
}
else if (p[i][j] == 1 && grupo[i] != grupo[j]) return 0;
}
linea[i].push_back(i);
}
rep(i, 0, n - 1){
rep(j, i + 1, n - 1){
if (p[i][j] == 2 && grupo[i] == grupo[j]) return 0; // LOS GRUPOS SON DE LINEAS, NO PUEDEN TENER 2 CAMINOS.
else if (p[i][j] == 0 && grupoCiclo[grupo[i]] == grupoCiclo[grupo[j]]) return 0;
else if (p[i][j] == 2){
if (!checaGrupos(grupoCiclo[i], grupoCiclo[j])) return 0;
else if (grupoCiclo[grupo[i]] == i && grupoCiclo[grupo[j]] == j){
ciclo[i].push_back(j);
grupoCiclo[grupo[j]] = grupo[i];
}
}
}
}
rep(i, 0, n - 1){
for(auto nodo : linea[i]){
puente(i, nodo);
}
}
rep(i, 0, n - 1){
if (ciclo[i].size() == 1) return 0; // NO PUEDE HABER UN CICLO DE SOLO 2 NODOS
if (ciclo[i].size() > 0){
rep(j, 0, ciclo[i].size() - 1){
if (j > 0) puente(ciclo[i][j], ciclo[i][j - 1]);
if (j < ciclo[i].size() - 1) puente(ciclo[i][j], ciclo[i][j + 1]);
}
puente(i, ciclo[i][0]);
puente(i, ciclo[i][ciclo[i].size() - 1]);
}
}
build(respuesta);
return 1;
}
