#include "supertrees.h"
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
//subtask 2: star graph, 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;
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);
}
}
// set<pair<int, int>> act;
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));
// // cout<<"ABORT";
// if(p[j][k]==0){
// // cout<<"j="<<j<<" k="<<k<<"\n";
// // cout<<"NOPE\n";
// return 0;
// }
}
}
}
// 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(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;
}
