#include "supertrees.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
int const N = 1010;
int par[N];
int m;
vector<vector<int>> ans;
int find(int n){
if(par[n] == n) return n;
else return par[n] = find(par[n]);
}
int nexti(int ind){
return (ind+1)%m;
}
int previ(int ind){
return (ind-1+m)%m;
}
void connect(int i,int j){
ans[i][j] = 1;
ans[j][i] = 1;
}
void unconnect(int i,int j){
ans[i][j] = 0;
ans[j][i] = 0;
}
void pullout(int i){
unconnect(i,previ(i));
unconnect(i,nexti(i));
connect(previ(i),nexti(i));
}
int construct(std::vector<std::vector<int>> p) {
m = p.size();
for(int i{};i < m;i++){
vector<int> temp(m,0);
ans.push_back(temp);
}
for(int i{};i < m;i++){
par[i] = i;
}
for(int i{};i < m;i++){
for(int j{};j < m;j++){
if(i == j) continue;
if(p[i][j]) par[find(i)] = find(j);
}
}
map<int,int> mp;
for(int i{};i < m;i++){
int fi = find(i);
if(mp.count(fi)){
connect(mp[fi],i);
mp[fi] = i;
}
else mp[fi] = i;
}
for(auto [a,b]:mp){
if(a != b) connect(a,b);
}
// for(int i{};i < m;i++){
// connect(i,previ(i));
// connect(i,nexti(i));
// }
// cout << ans.size();
// cout << endl << ans[0].size() << endl;
for(int i{};i < m;i++){
for(int j{};j < m;j++){
if(i == j) continue;
if(i < j && p[i][j] == 1){
pullout(i);
connect(i,j);
}
}
}
build(ans);
return 1;
}
