#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
const int mxN = 2005;
vector<int> adj[mxN];
vector<vector<int>> ways(mxN,vector<int>(mxN,0));
bool vis[mxN];
/*vector<vector<int>> nways(mxN,vector<int>(mxN,0));*/
struct DSU{
vector<int> sz,par;
void init(int n){
sz.resize(n,1);
par.resize(n);
for(int i=1;i<n;++i) par[i]=i;
}
int findPar(int u){
if(par[u]==u) return u;
return par[u]=findPar(par[u]);
}
void unite(int u,int v){
int upar=findPar(u);
int vpar=findPar(v);
if(upar==vpar) return;
if(sz[upar]>sz[vpar]){
par[vpar]=upar;
sz[upar]+=sz[vpar];
}else{
par[upar]=vpar;
sz[vpar]+=sz[upar];
}
}
bool same(int u,int v){
return findPar(u)==findPar(v);
}
} ds;
void dfs(int u,int lead){
++ways[lead][u];
vis[u]=1;
for(auto it:adj[u]){
if(!vis[it]) dfs(it,lead);
}
vis[u]=0;
}
/*void dfs2(int u,int lead){
++nways[lead][u];
vis[u]=1;
for(auto it:adj[u]){
if(!vis[it]) dfs(it,lead);
}
vis[u]=0;
}*/
/*
void build(vector<vector<int>> cadj){
int n=cadj.size();
for(int i=0;i<n;++i){
dfs2(i,i);
for(int j=0;j<n;++j){
vis[j]=0;
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cout<<ways[i][j]<<" ";
}cout<<endl;
}
}
*/
int construct(vector<vector<int>> p){
int n=p.size();
ds.init(n+6);
vector<vector<int>> current_adj(n,vector<int>(n,0));
for(int i=0;i<n;++i){
vector<int> one_way={i};
for(int j=0;j<n;++j){
if(!ds.same(i,j)&&p[i][j]==1){
ds.unite(i,j);
current_adj[one_way.back()][j]=1;
current_adj[j][one_way.back()]=1;
one_way.pb(j);
}
}
}
for(int i=0;i<n;++i){
vector<int> two_way={i};
for(int j=0;j<n;++j){
ways[i][j]=0;
if(!ds.same(i,j)&&p[i][j]==2){
ds.unite(i,j);
current_adj[two_way.back()][j]=1;
current_adj[j][two_way.back()]=1;
two_way.pb(j);
}
}
if(two_way.size()>1){
current_adj[two_way.back()][i]=1;
current_adj[i][two_way.back()]=1;
}
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(current_adj[i][j]){
adj[i].pb(j);
adj[j].pb(i);
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j) vis[j]=0;
dfs(i,i);
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(ways[i][j]!=p[i][j]) return 0;
}
}
build(current_adj);
return 1;
}
/*
int main() {
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m,u,v;cin>>n>>m;
for(int i=0;i<m;++i){
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
ways.resize(n,vector<int>(n,0));
for(int i=0;i<n;++i){
dfs(i,i);
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cout<<ways[i][j]<<" ";
}cout<<endl;
}
construct(ways);
return 0;
}*/
