#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
vector<vector<int>> ans, kl, tr; vector<vector<char>> w;
queue<int> h; vector<char> vis; vector<int> dist, li, ns, qh; int t=0;
void dfs(int u, int p)
{
vis[u]=1; h.push(u); ns[u]=t++;
for(auto x: kl[u])
{
if(x==p)continue;if(vis[x])continue; w[u][x]=0; w[x][u]=0;
dist[x]=dist[u]+1; tr[u].push_back(x); dfs(x, u); h.push(u);
}
qh[u]=t;li.push_back(u);
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
kl.assign(n+1, vector<int>()); vector<int> o(n+1, 0), uw;
ns.assign(n+1, 0); qh.assign(n+1, 0); t=0;
vis.assign(n+1, 0); tr.assign(n+1, vector<int> ()); dist.assign(n+1, 0);
while(!h.empty())h.pop(); w.assign(n+1, vector<char>(n+1, 0));
for(ll i=0; i<m; i++)
{
kl[a[i]].push_back(b[i]); kl[b[i]].push_back(a[i]);
w[a[i]][b[i]]=1; w[b[i]][a[i]]=1;
} li.clear();
for(int i=1; i<=n; i++){sort(kl[i].begin(), kl[i].end());}
for(int i=1; i<=n; i++){if(!vis[i]){dist[i]=0;dfs(i, 0);}}
int y=(h.size())+2*n; ans.assign(3*n, vector<int>(3*n, -1)); int j=0;
vector<vector<int>> di; vector<vector<pair<int, int>>> t(n+1);
while(!h.empty())
{
int u=h.front(); h.pop(); vector<int> g(y, u); di.push_back(g);
uw.push_back(u);
if(o[u]==0)
{
vector<int> p(y, u);int i=1, xd=di.size();
for(int c=ns[u]+1; c<qh[u]; c+=2)
{
if(c>=y)break; t[u].push_back({xd, c});
}
di.push_back(p); uw.push_back(u);
vector<int> l(y, u);di.push_back(l);uw.push_back(u);
}
o[u]++;
}
for(int i=1; i<=n; i++)
{
for(auto x: tr[i])
{
if(t[i].empty())continue;
di[t[i].back().F][t[i].back().S]=x; t[i].pop_back();
}
}
for(auto i: li)
{
for(int j=1; j<=n; j++)
{
if(!w[i][j])continue; w[i][j]=0; w[j][i]=0; if(t[j].empty())continue;
if(t[j].back().F+1<di.size())
{
di[t[j].back().F+1][t[j].back().S]=di[t[j].back().F][t[j].back().S];
}
di[t[j].back().F+1][t[j].back().S]=i; t[j].pop_back();
}
}
int us=0;
for(int i=0; i<di.size(); i++)
{
if(us==3*n)break; if((dist[uw[i]]+i)%2!=0)continue;
for(int j=0; j<3*n; j++){ans[j][(j+i)%(3*n)]=di[i][j];}
us++;
}
if(us<3*n)
{
for(int i=0; i<di.size()&&us<3*n; i++)
{
if((dist[uw[i]]+i)%2==0)continue;
for(int j=0; j<3*n; j++){ans[j][(j+i)%(3*n)]=di[i][j];}
us++;
}
}
return ans;
}
