#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int TAILLEMAXI=1002;
int nbpers,couleur,pb;
int dejavu[TAILLEMAXI];
int num[TAILLEMAXI];
int nbchem[TAILLEMAXI][TAILLEMAXI];
vector<int> ec;
vector<int> compo[TAILLEMAXI];
vector<int> un[TAILLEMAXI];
int rep[TAILLEMAXI][TAILLEMAXI];
vector<vector<int>> r;
vector<int> deux;
void dfs1(int n){
if (dejavu[n]==1){
return ;
}
dejavu[n]=1;
num[n]=couleur;
ec.push_back(n);
for (int i=0;i<nbpers;i++){
if (nbchem[n][i]>0){
dfs1(i);
}
}
}
void dfs2(int n){
if (dejavu[n]==1){
return ;
}
dejavu[n]=1;
ec.push_back(n);
for (int i=0;i<nbpers;i++){
if (nbchem[n][i]==1){
dfs2(i);
}
}
}
int construct(vector<vector<int>> c) {
nbpers=c.size();
for (int i=0;i<nbpers;i++){
for (int j=0;j<nbpers;j++){
nbchem[i][j]=c[i][j];
}
}
for (int i=0;i<nbpers;i++){
if (dejavu[i]==0){
ec.clear();
dfs1(i);
compo[couleur]=ec;
couleur++;
}
}
for (int j=0;j<nbpers;j++){
dejavu[j]=0;
}
for (int i=0;i<couleur;i++){
deux.clear();
for (int ipers=0;ipers<(int)compo[i].size();ipers++){
if (dejavu[compo[i][ipers]]==0){
deux.push_back(compo[i][ipers]);
}
ec.clear();
dfs2(compo[i][ipers]);
un[compo[i][ipers]]=ec;
if (ec.size()>1) {
for (int ilien=0;ilien<(int)un[compo[i][ipers]].size()-1;ilien++){
rep[un[compo[i][ipers]][ilien]][un[compo[i][ipers]][ilien+1]]=1;
rep[un[compo[i][ipers]][ilien+1]][un[compo[i][ipers]][ilien]]=1;
}
}
}
for (int ideux=0;ideux<(int)deux.size()-1;ideux++){
rep[deux[ideux]][deux[ideux+1]]=1;
rep[deux[ideux+1]][deux[ideux]]=1;
}
if (deux.size()>2){
rep[deux[0]][deux[deux.size()-1]]=1;
rep[deux[deux.size()-1]][deux[0]]=1;
}
}
for (int i=0;i<nbpers;i++){
ec.clear();
for (int j=0;j<nbpers;j++){
if (rep[i][j]==1){
ec.push_back(1);
}
else {
ec.push_back(0);
}
}
r.push_back(ec);
}
build(r);
return 1;
}
