#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int> > adj;
vector<bool> visited;
bool cycle = false;
vector<int> parent;
void dfs(int u, int p){
if(visited[u]){
cycle = true;
return;
}
visited[u] = true;
for(int v : adj[u]){
if(v != p){
parent[v] = u;
dfs(v, u);
}
}
}
int construct(vector<vector<int> > p){
n = p.size();
adj.resize(n);
visited.resize(n, false);
parent.resize(n);
bool has1 = false;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(p[i][j] == 1){
adj[i].push_back(j);
adj[j].push_back(i);
has1 = true;
}
}
}
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs(i, -1);
}
}
if(!cycle){
vector<vector<int> > answer(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
answer[i][parent[i]] = 1;
answer[parent[i]][i] = 1;
}
build(answer);
return 1;
}
else{
return 0;
}
}
