#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int MX = 1e3+5;
int W[MX][MX];
int pa[2][MX];
int tp[2][MX];
/*void build(vector<vector<int>> sk)
{
cout << "Check out this graph: " << endl;
int n = sk.size(); cout << "size = " << n << endl;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
cout << sk[i][j] << " ";
cout << endl;
}
}*/
int leader(int u, int s)
{
if(pa[s][u] < 0)
return u;
else
return pa[s][u] = leader(pa[s][u], s);
}
void merge(int u, int v, int Wr, int s)
{
u = leader(u, s);
v = leader(v, s);
if(u == v)
{
tp[s][v] = max(tp[s][v], Wr);
return;
}
if(pa[s][u] < pa[s][v])
swap(u, v);
pa[s][v]+=pa[s][u];
pa[s][u] = v;
tp[s][v] = max(tp[s][v], max(Wr, tp[s][u]));
return;
}
int construct(vector<vector<int>> W)
{
int n = W.size();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 2; j++)
{
pa[j][i] = -1;
tp[j][i] = 1;
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(W[i][j])
merge(i, j, W[i][j], 0);
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(W[i][j] == 0)
continue;
if(W[i][j] == 1)
merge(i, j, 0, 1);
}
}
bool stuff = 1;
vector<int> comp[2][n+1];
for(int i = 0; i < n; i++)
{
for(int s = 0; s < 2; s++)
comp[s][leader(i, s)].pb(i);
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if((i==j))
{
stuff = stuff&(W[i][j] == 1);
//cout << "nval: " << stuff << endl;
continue;
}
int expect = (leader(i, 0) == leader(j, 0))? ((leader(i, 1) == leader(j, 1))? 1 : tp[0][leader(i, 0)]) : 0;
//cout << "For i = " << i << " and j = " << j << " we expect = " << expect << endl;
stuff = stuff&(W[i][j] == expect);
//cout << "nval: " << stuff << endl;
}
}
vector<in> edges;
for(int i = 0; i < n; i++)
{
if(leader(i, 0) != i)
continue;
set<int> sp;
for(int x: comp[0][i])
sp.insert(leader(x, 1));
vector<int> dew;
for(auto x: sp)
{
for(int T = 1; T < comp[1][x].size(); T++)
edges.pb({comp[1][x][T-1], comp[1][x][T]});
dew.pb(x);
}
int Ww = tp[0][i];
if(Ww == 3)
{
if(sp.size() < 4)
{
//cout << "size of level 3 comp is < 4" << endl;
stuff = 0;
break;
}
for(int i = 0; i < 3; i++)
edges.pb({dew[i], dew[(i+1)%3]});
for(int i = 3; i < dew.size(); i++)
edges.pb({dew[i-1], dew[i]});
edges.pb({dew[dew.size()-1], dew[0]});
}
else if(Ww == 2)
{
if(sp.size() < 3)
{
//cout << "size of level 2 comp is < 3" << endl;
stuff = 0;
break;
}
int N = dew.size();
for(int i = 0; i < N; i++)
edges.pb({dew[i], dew[(i+1)%N]});
}
}
if(stuff == 0)
return 0;
vector<vector<int>> ans(n, vector<int> (n, 0));
for(auto [u, v]: edges)
ans[u][v] = ans[v][u] = 1;
build(ans);
return 1;
}
/*signed main()
{
int n; cin >> n;
vector<vector<int>> ways;
ways.resize(n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
int x; cin >> x;
ways[i].pb(x);
}
}
cout << construct(ways) << endl;
return 0;
}*/
