#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1050;
vector<int>E[N];
bool was[N];vector<int>temp;
void DFS(int u){
was[u]=true;
temp.pb(u);
for(auto i:E[u]) if(!was[i]) DFS(i);
}
vector<pair<int,int>>edges;
vector<vector<int>>res;
int construct(std::vector<std::vector<int>> p){
int n=p.size();
for(int i=0;i<n;i++){
if(p[i][i]!=1) return 0;
for(int j=0;j<n;j++){
if(p[i][j]!=p[j][i]||p[i][j]==3) return 0;
if(i!=j&&p[i][j]!=0) E[i].pb(j);
}
}
vector<vector<int>>komp;
for(int i=0;i<n;i++){
if(!was[i]){
temp.clear();
DFS(i);
komp.pb(temp);
temp.clear();
}
}
for(int i=0;i<n;i++) E[i].clear(),was[i]=false;
for(auto ind:komp){
//for(auto i:ind) printf("%i ",i);printf("\n");
for(auto i:ind){
for(auto j:ind){
if(p[i][j]==1&&i!=j) E[i].pb(j);
}
}
vector<vector<int>>stabla;
for(auto i:ind){
if(!was[i]){
temp.clear();
DFS(i);
stabla.pb(temp);
temp.clear();
}
}
for(auto idx:stabla){
for(auto i:idx){
for(auto j:idx){
if(p[i][j]!=1) return 0;
}
}
}
//printf("%i\n",stabla.size());
//for(auto idx:stabla){for(auto i:idx) printf("%i ",i);printf("\n");}
for(auto idx:stabla){
for(int i=1;i<idx.size();i++) edges.pb({idx[i-1],idx[i]});
}
vector<int>ciklus;for(auto idx:stabla) ciklus.pb(idx[0]);
if(ciklus.size()>1){
for(int i=1;i<ciklus.size();i++) edges.pb({ciklus[i-1],ciklus[i]});
edges.pb({ciklus.back(),ciklus[0]});
}
for(auto i:ind) E[i].clear(),was[i]=false;
}
res.resize(n);for(int i=0;i<n;i++) res[i].resize(n);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) res[i][j]=0;
//for(auto [u,v]:edges) printf("{%i %i} ",u,v);printf("\n");
for(auto [u,v]:edges) res[u][v]=res[v][u]=1;
build(res);
return 1;
}
