#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 t3=0, k=1;
vector<vector<pair<int, int>>> t;
void dfs(int u, int p)
{
vis[u]=1; ans[0][t3++]=u; h.push(u); int l=t3, r=l;
for(auto x: kl[u])
{
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); ans[0][t3++]=u; r=t3;
}
li.push_back(u); if(r==l) return;
for(int i=l; i<r; i++){ans[k][i]=u;ans[k+1][i]=u;}
for(int i=l+1; i<r; i+=2)t[u].push_back({k+1, i}); k+=2;
}
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); t3=0;
vis.assign(n+1, 0); tr.resize(n+1); dist.assign(n+1, 0);
while(!h.empty())h.pop(); w.assign(n+1, vector<char>(n+1));
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;
}
ans.assign(2*n, vector<int>(2*n)); int j=0;
t.resize(n+1); dfs(1, 0);
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!=2*n-1)
{
ans[t[j].back().F+1][t[j].back().S]=ans[t[j].back().F][t[j].back().S];
}
ans[t[j].back().F+1][t[j].back().S]=i; t[j].pop_back();
}
}
for(int i=1; i<ans.size(); i++)
{
for(int j=0; j<ans.size(); j++){if(ans[i][j]==0)ans[i][j]=ans[i-1][j];}
}
for(int i=0; i<2*n; i++)ans[i][2*n-1]=ans[i][2*n-2];
return ans;
}
