#include<bits/stdc++.h>
#include "supertrees.h"
#include <vector>
#define pb push_back
using namespace std;
void dfs(int a, int cl, vector<bool>& mk, vector<int>& scc, vector<int> v[], vector<vector<int>>& answer){
mk[a]=true;
scc[a]=cl;
for(auto b:v[a]){
if(!mk[b]){ answer[a][b]=answer[b][a]=1; dfs(b, cl, mk, scc, v, answer); }
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
vector<int> scc(n), v[n];
vector<bool> mk(n, 0);
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
bool ans=true;
for(int i=0; i<n-1; i++){
for(int j=i+1; j<n; j++){
if(i==j) continue;
if(p[i][j]==1&&!mk[j]){
v[i].pb(j);
v[j].pb(i);
mk[j]=true;
}
}
}
for(int i=0; i<n; i++) mk[i]=0;
int id=0;
for(int i=0; i<n; i++){
if(!mk[i]){ dfs(i, id, mk, scc, v, answer); id++; }
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if((p[i][j]==1&&scc[i]!=scc[j])||(p[i][j]==0&&scc[i]==scc[j])) ans=false;
}
}
if(ans) build(answer);
return ans;
}
