#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int P[1005][1005];
bool vis[1005];
int mx,N;
vector<int> comp,cyc;
vector<int> tree;
vector<bool> vis2;
void dfs(int u, int p){
vis[u] = 1; comp.push_back(u);
for(int i = 0;i<N;++i){
mx = max(mx,P[u][i]);
if(!vis[i] && P[u][i] > 0){
dfs(i,u);
}
}
}
void dfs2(int u, int p){
vis2[u] = 1; tree.push_back(u);
for(auto v : comp){
if(!vis2[v] && P[u][v] == 1){
dfs2(v,u);
}
}
}
int construct(vector<vector<int>> p){
memset(vis,false,sizeof(vis));
N = p.size();
vector<vector<int>> ans(N,vector<int>(N,0));
for(int i = 0;i<N;++i){
for(int j = 0;j<N;++j){
P[i][j] = p[i][j];
}
}
for(int i = 0;i<N;++i){
if(!vis[i]){
mx = 1; comp.clear();
dfs(i,-1);
if(mx == 3) return 0;
for(int j = 0;j<comp.size();++j){
for(int k = 0;k<j;++k){
if(P[comp[j]][comp[k]] == 0){
return 0;
}
}
}
if(mx == 1){
for(int j = 1;j<comp.size();++j){
ans[comp[j-1]][comp[j]] = ans[comp[j]][comp[j-1]] = 1;
}
//build(ans);
/*for(int j = 0;j<ans.size();++j){
for(int k = 0;k<ans.size();++k){
cout << ans[j][k] << " ";
}
cout << "\n";
}*/
continue;
}
//mx = 2
vis2 = vector<bool>(N,false); cyc.clear();
for(int j = 0;j<comp.size();++j){
if(!vis2[comp[j]]){
tree.clear();
dfs2(comp[j],-1);
for(int k = 1;k<tree.size();++k){
for(int l = 0;l<k;++l){
if(P[tree[k]][tree[l]] != 1) return 0;
}
ans[tree[0]][tree[k]] = ans[tree[k]][tree[0]] = 1;
}
cyc.push_back(tree[0]);
}
}
if(cyc.size() <= 2) return 0;
for(int j = 1;j<cyc.size();++j){
ans[cyc[j-1]][cyc[j]] = ans[cyc[j]][cyc[j-1]] = 1;
}
ans[cyc.back()][cyc[0]] = ans[cyc[0]][cyc.back()] = 1;
//build(ans);
/*for(int j = 0;j<ans.size();++j){
for(int k = 0;k<ans.size();++k){
cout << ans[j][k] << " ";
}
cout << "\n";
}*/
}
}
build(ans);
return 1;
}
