#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
/*
void build(vector<vector<int>> v){
for (int i=0; i<v.size(); i++){
for (int j=0; j<v.size(); j++){
cout<<v[i][j]<<' ';
}
cout<<"\n";
}
}
*/
vector <int> visited(1005);
pair<int,vector <int>> fc(int i, vector<vector<int>> p){
vector <int> tm;
int ans=0;
tm.push_back(i);
if (visited[i]==0){
visited[i]=1;
for (int j=0; j<p.size(); j++){
if (p[i][j]==1 && visited[j]==0 && i!=j){
//tm.push_back(j);
ans++;
pair<int,vector <int>> tt;
tt=fc(j,p);
ans+=tt.first;
for (int t=0; t<tt.second.size(); t++){
tm.push_back(tt.second[t]);
}
}
}
}
//cout<<ans<<' ';
return {ans,tm};
}
int construct(vector<vector<int>> p){
int n=p.size();
vector<vector<int>> arr(n);
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (p[i][j]!=p[j][i]){return 0;}
if (i==j){p[i][i]=0;}
arr[i].push_back(0);
}
}
vector <vector<int>> tree(n);
for (int i=0; i<n; i++){visited[i]=0;}
int k=0;
for (int i=0; i<n; i++){
if (visited[i]==0){
pair<int,vector <int>> tt;
tt=fc(i,p);
if (tt.first+1!=tt.second.size()){cout<<"HELLO";return 0;}
for (int i=0; i<tt.second.size(); i++){
tree[k].push_back(tt.second[i]);
}
k++;
}
}
for (int i=0; i<k; i++){
for (int j=0; j<tree[i].size()-1; j++){
arr[tree[i][j]][tree[i][j+1]]=1;
arr[tree[i][j+1]][tree[i][j]]=1;
}
}
build(arr);
return 1;
}
