#include "worldmap.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<vector<int>>create_map(int n,int m,vector<int>a,vector<int>b){
vector<int>g[n],tour,ra,rb,depth(n),rank(n,-1),holder(n,-1),h[n];
for(int i=0;i<m;i++)a[i]--,b[i]--,g[a[i]].push_back(b[i]),g[b[i]].push_back(a[i]);
int vis[n]={},cur=0,parity=0;
function<void(int)>dfs=[&](int x){
vis[x]=1,tour.push_back(x);
for(int i:g[x]){
if(!vis[i])depth[i]=depth[x]+1,dfs(i),tour.push_back(x);
else if(depth[x]<depth[i])ra.push_back(x),rb.push_back(i);
}
};
dfs(0);
for(int i=0,d;i<2*n-1;i++)d=min(i,2*n-2-i),rank[tour[i]]<d?rank[tour[i]]=d,holder[tour[i]]=i:0;
for(int i=0;i<m-(n-1);i++){
if(rank[ra[i]]<rank[rb[i]])swap(ra[i],rb[i]);
h[ra[i]].push_back(rb[i]);
}
int k=2*n;
vector<vector<int>>ans(k,vector<int>(k));
for(int i=0;i<2*n-1;i++){
if(i==holder[tour[i]]){
int pos=0;
for(int j=0;j<k;j++){
int ya=cur-j,yb=cur+1-j,yc=cur+2-j;
if(ya>=0&&ya<k)ans[j][ya]=tour[i];
if(yb>=0&&yb<k)pos<int(h[tour[i]].size())?(ans[j][yb]=h[tour[i]][pos],pos++):ans[j][yb]=tour[i];
if(yc>=0&&yc<k)ans[j][yc]=tour[i];
}
cur+=3,parity^=1;
}else{
for(int j=0,ya;j<k;j++)ya=cur-j,ya>=0&&ya<k?ans[j][ya]=tour[i]:0;
cur++;
}
}
for(int i=0;i<k;i++)for(int j=0;j<k;j++)ans[i][j]++;
return ans;
}
