#include "supertrees.h"
#include <vector>
#include <map>
#include <iostream>
#include <bitset>
using namespace std;
int const N = 1010;
int par[N];
int m;
using pii = pair<int,int>;
vector<vector<int>> ans;
bitset<N> getout;
#define f first
#define s second
int nextval[N];
int prevval[N];
int find(int n){
if(par[n] == n) return n;
else return par[n] = find(par[n]);
}
int nexti(int ind){
return nextval[ind];
}
int previ(int ind){
return prevval[ind];
}
void connect(int i,int j){
//cout << i << " " << j << endl;
if(i == j || find(i) != find(j)) return;
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));
nextval[previ(i)] = nexti(i);
prevval[nexti(i)] = previ(i);
// cout << i << "pre=" << previ(i) << endl;
// cout << i << "next=" << nexti(i) << endl;
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,pii> mp;
for(int i{};i < m;i++){
int fi = find(i);
//cout << fi << " ";
if(mp.count(fi)){
nextval[mp[fi].f] = i;
prevval[i] = mp[fi].f;
//cout << fi << "-" << i << endl;
connect(mp[fi].f,i);
mp[fi] = {i,mp[fi].s};
}
else mp[fi] = {i,i};
}
//cout << endl;
for(auto [a,b]:mp){
if(b.s != b.f){
nextval[b.f] = b.s;
prevval[b.s] = b.f;
//cout << b.f << " " << b.s << endl;
connect(b.f,b.s);
}
}
// for(int i{};i < m;i++){
// connect(i,previ(i));
// connect(i,nexti(i));
// }
// cout << ans.size();
// cout << endl << ans[0].size() << endl;
// cout << nexti(1);
// cout << previ(3);
for(int i{};i < m;i++){
for(int j{};j < m;j++){
if(i == j) continue;
if(getout[i] || getout[j]) continue;
if(i < j && p[i][j] == 1){
//cout << i << "=" << j << endl;
pullout(i);
getout[i] = 1;;
connect(i,j);
}
}
}
build(ans);
return 1;
}
