#include "supertrees.h"
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
//subtask 4
int n = p.size();
vector<vector<int>> ans(n, vector<int> (n));
// vector<int> ifstar(n);
// vector<int> ifflag(n);
set<int> flagstar;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
ans[i][j] = 0;
}
}
map<int, vector<int>> cc1;
vector<int> flags1;
map<int, vector<int>> cc2;
vector<int> flags2;
flags1.push_back(0);
cc1[0].push_back(0);
flags2.push_back(0);
cc2[0].push_back(0);
for(int i=1; i<n; i++){
int tmp1, tmp2;
tmp1 = tmp2 = 0;
for(int j: flags1){
if(i==j) continue;
if(p[i][j]==0) continue;
else if(p[i][j]==1){
cc1[j].push_back(i);
tmp1++;
}
else{
cc2[j].push_back(i);
tmp2++;
}
}
if(tmp1==0){
flags1.push_back(i);
cc1[i].push_back(i);
}
if(tmp2==0){
flags2.push_back(i);
cc2[i].push_back(i);
}
}
//star <3
for(auto i: cc1){
// cout<<i.first<<"!";
// for(int j: i.second) cout<<j<<" ";
// cout<<"\n";
flagstar.insert(i.second[0]);
int sz = i.second.size();
// cout<<sz<<"\n";
if(sz==0 || sz==1) continue;
for(int j=1; j<sz; j++){
ans[i.second[0]][i.second[j]] = 1;
ans[i.second[j]][i.second[0]] = 1;
}
}
// cout<<"flagstar\n";
// for(int i: flagstar) cout<<i<<" ";
// cout<<"\n";
//cycles
for(auto i: cc2){
// cout<<i.first<<"!";
// for(int j: i.second) cout<<j<<" ";
// cout<<"\n";
int sz = i.second.size();
// cout<<sz<<"\n";
if(sz==0 || sz==1) continue;
vector<int> v;
for(int j: i.second){
if(flagstar.count(j)) v.push_back(j);
}
// cout<<"v\n";
// cout<<i.first<<" | ";
// for(int j: v) cout<<j<<" ";
// cout<<"\n";
sz = v.size();
if(sz<=2) continue;
for(int j=1; j<sz; j++){
ans[v[j]][v[j-1]] = 1;
ans[v[j-1]][v[j]] = 1;
}
ans[v[0]][v[sz-1]] = 1;
ans[v[sz-1]][v[0]] = 1;
}
// set<pair<int,int>> act;
// for(auto i: cc){
// // cout<<"i.first="<<i.first<<"\n";
// for(int j: i.second){
// for(int k: i.second){
// act.insert(make_pair(j, k));
// act.insert(make_pair(k, j));
// }
// }
// }
// // for(auto i: act) cout<<i.first<<" "<<i.second<<"\n";
// // cout<<"\n";
// // sort(act.begin(), act.end());
// for(int i=0; i<n; i++){
// for(int j=0; j<n; j++){
// // cout<<"here";
// if(i==j) continue;
// if(p[i][j]==0){
// if(act.count({i,j})==1) return 0;
// }
// else{
// if(act.count({i,j})==0) return 0;
// }
// }
// }
build(ans);
return 1;
}
