#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MAXN=1e3+1;
bool gone[MAXN];
int pathnum[MAXN][MAXN];
int n;
vector<vector<int>> comps;
void dfs(int loc){
comps.back().push_back(loc);
gone[loc]=true;
for(int i=0;i<n;i++){
if(pathnum[loc][i]&&!gone[i]){
dfs(i);
}
}
}
vector<vector<vector<int>>> comps2;
void dfs2(int loc){
comps2.back().back().push_back(loc);
gone[loc]=true;
for(int i=0;i<n;i++){
if(pathnum[loc][i]==1&&!gone[i]){
dfs2(i);
}
}
}
int construct(vector<vector<int>> p){
n=sz(p);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)pathnum[i][j]=p[i][j];
for(int i=0;i<n;i++){
if(!gone[i]){
comps.push_back({});
dfs(i);
}
}
for(auto x:comps){
for(int i=0;i<sz(x);i++)for(int j=i+1;j<sz(x);j++){
if(!pathnum[x[i]][x[j]])return 0;
}
}
fill(gone,gone+n,false);
for(auto x:comps){
comps2.push_back({});
for(auto y:x){
if(!gone[y]){
comps2.back().push_back({});
dfs2(y);
}
}
}
for(auto y:comps2){
for(auto x:y){
for(int i=0;i<sz(x);i++)for(int j=i+1;j<sz(x);j++){
if(pathnum[x[i]][x[j]]!=1)return 0;
}
}
for(int i=0;i<sz(y);i++){
for(int j=i+1;j<sz(y);j++){
for(auto x:y[i]){
for(auto z:y[j]){
if(pathnum[x][z]!=2)return 0;
}
}
}
}
}
vector<vector<int>> adj(n,vector<int>(n,0));
auto addedge=[&](int l, int r){
adj[l][r]=1,adj[r][l]=1;
};
for(auto x:comps2){
if(sz(x)==2)return 0;
for(int i=0;i<sz(x);i++){
if(sz(x)>1)addedge(x[i].back(),x[(i+1)%sz(x)].back());
for(int j=1;j<sz(x[i]);j++){
addedge(x[i][j-1],x[i][j]);
}
}
}
build(adj);
return 1;
}
