#include "supertrees.h"
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
//subtask 3: mini cycles, but as connected components
int n = p.size();
vector<vector<int>> ans(n, vector<int> (n));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
ans[i][j] = 0;
}
}
map<int, vector<int>> cc;
vector<int> flags;
flags.push_back(0);
cc[0].push_back(0);
for(int i=1; i<n; i++){
int tmp = 0;
for(int j: flags){
if(p[i][j]==0) continue;
if(i==j) continue;
// ans[i][j] = 1;
// ans[j][i] = 1;
cc[j].push_back(i);
tmp++;
// break;
}
if(tmp>=2) return 0;
if(tmp==0){
flags.push_back(i);
cc[i].push_back(i);
}
}
for(auto i: cc){
// for(int j: i.second) cout<<j<<" ";
// cout<<"\n";
int sz = i.second.size();
if(sz==0 || sz==1) continue;
if(sz==2) return 0;
for(int j=1; j<sz; j++){
ans[j][j-1] = 1;
ans[j-1][j] = 1;
}
ans[0][sz-1] = 1;
ans[sz-1][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;
}
