#include <bits/stdc++.h>
#include "supertrees.h"
///void build(std::vector<std::vector<int>> _b);
#define MAX 1005
int pai[MAX][10];
int find(int a,int b){
if(pai[a][b]==a){
return a;
}
return pai[a][b]=find(pai[a][b],b);
}
void Union(int a,int b,int c){
a=find(a,c);
b=find(b,c);
pai[a][c]=b;
}
void ativar(int a,int b,std::vector<std::vector<int>>& ref){
ref[a][b]=ref[b][a]=1;
/// printf("Constroi %d %d\n",a,b);
}
int construct(std::vector<std::vector<int>> p) {
std::vector<std::vector<int>> answer;
int n = p.size();
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i=0;i!=10;++i){
for(int j=0;j!=MAX;++j)
pai[j][i]=j;
}
int N = p.size();
bool emciclo[N]={};
for(int i=0;i!=N;++i){
for(int j=0;j!=N;++j){
if(p[i][j]==3)return 0;///Impossivel 3 caminhos
if(p[i][j]!=p[j][i])return 0;
if(p[i][j]==2){///Em ciclo
Union(i,j,1);
emciclo[i]=emciclo[j]=1;
}
if(p[i][j]==1){///Conexao direta
Union(i,j,4);
}
if(p[i][j]!=0){///Conectado
Union(i,j,0);
}
}
}
///Construir arvore
{
std::map<int,std::vector<int>> grupos;
for(int i=0;i!=N;++i){
grupos[find(i,4)].push_back(i);
}
for(auto&x:grupos){
if(x.second.size()==1)continue;
std::vector<int> copia;
copia=x.second;
for(int i=1;i<copia.size();++i){
if(find(copia[0],7)!=find(copia[i],7)){
Union(copia[0],copia[i],7);
ativar(copia[i],copia[0],answer);
}
}
}
}
/// printf("Arvores inauguradas!\n");
///Construir ciclos
{
std::map<int,std::vector<int>> grupos;
for(int i=0;i!=N;++i){
if(!emciclo[i])continue;
if(find(i,7)!=i)continue;
grupos[find(i,1)].push_back(i);
}
for(auto&x:grupos){
if(x.second.size()<3)return 0;
std::vector<int> copia;
copia=x.second;
for(int i=1;i<copia.size();++i){
if(find(copia[i],7)!=find(copia[i-1],7)){
Union(copia[i],copia[i-1],7);
ativar(copia[i],copia[i-1],answer);
}
}
Union(copia[0],copia[copia.size()-1],7);
ativar(copia[0],copia[copia.size()-1],answer);
}
}
build(answer);
return 1;
}
