#include "supertrees.h"
#include <vector>
#include <map>
#include <iostream>
#include <bitset>
using namespace std;
int const N = 1010;
using pii = pair<int,int>;
pii par[N];
int m;
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].f == n) return n;
else return par[n].f = find(par[n].f);
}
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,0};
}
for(int i{};i < m;i++){
for(int j{};j < m;j++){
// for(int i{};i < m;i++){
// cout << par[i].f << "-" << par[i].s << " ";
// }
// cout << endl;
if(i == j) continue;
if(p[i][j] != p[j][i]){
//cout << -1;
return 0;
}
if(p[i][j]){
int fi = find(i);
int fj = find(j);
if(fi != fj){
par[fj].f = fi;
par[fi].s += par[fj].s;
}
if(p[i][j] == 2){
par[fi].s++;
}
}
}
}
map<int,pii> mp;
for(int i{};i < m;i++){
int fi = find(i);
//cout << par[fi].s << endl;
if(par[fi].s == 2) return 0;
//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);
}
}
}
for(int i{};i < m;i++){
if(p[i][i] != 1) return 0;
for(int j{};j < m;j++){
if(i == j) continue;
if(find(i) != find(j)){
if(p[i][j] != 0){
//cout << -1 << endl;
return 0;
}
else continue;
}
if(p[i][j] == 0){
if(find(i) == find(j)) return 0;
}
if(p[i][j] == 2){
if(getout[i]){
if(!getout[j] && ans[i][j]){
//cout << 1;
return 0;
}
}
}
if(p[i][j] == 1){
if(!getout[i] && !getout[j]){
// cout << i << " "<< j << endl;
// cout << 1 << endl;
return 0;
}
}
}
}
build(ans);
return 1;
}
