#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; vector<vector<char>> w;
vector<char> vis; vector<int> li; int t3=0, k=1;
vector<vector<pair<int, int>>> t;vector<int> l, r;
void dfs(int u, int p)
{
vis[u]=1; l[u]=t3;ans[0][t3++]=u;
for(auto x:kl[u])
{
if(vis[x])continue; w[x][u]=0; w[u][x]=0; dfs(x, u);
ans[0][t3++]=u;
}
r[u]=t3;li.push_back(u);
if(r[u]==l[u]+1)return;
for(int i=l[u]; i<r[u]; i++){ans[k][i]=u;ans[k+1][i]=u;}
for(int i=l[u]+1; i<r[u]; 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;
t3=0; k=1; li.clear(); vis.assign(n+1, 0);
w.assign(n+1, vector<char>(n+1, 0));l.resize(kl.size()); r.resize(kl.size());
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.assign(n+1, vector<pair<int, int>>()); 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][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;
}
