#include <bits/stdc++.h>
#include "worldmap.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int N=50;
vector<int> g[N];
vector<pair<int,vector<int>>> r;
int d[N];
void dfs(int v){
d[v]=1;
vector<int> i;
for(auto au : g[v]){
if(d[au]) continue;
else i.pb(au);
}
if(i.size()==0) return;
r.pb({0,{v}});
r.pb({1,i});
r.pb({0,{v}});
for(auto au : g[v]){
if(d[au]) continue;
dfs(au);
if(*(r.end()-1)!=pair<int,vector<int>>({0,{v}})) r.pb({0,{v}});
}
return;
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){
if(n==1){
vector<vector<int>> ans(1,vector<int>(1,1));
return ans;
}
r.clear();
for(int i=1; i<=n; i++){
g[i].clear();
d[i]=0;
}
for(int i=0; i<m; i++){
g[a[i]].pb(b[i]);
g[b[i]].pb(a[i]);
}
dfs(1);
int si=r.size(),si2=0;
while(r[si-1].fi==0){
r.erase(prev(r.end()));
si--;
if(si==1) break;
}
for(int i=0; i<si; i++){
if(r[i].fi==1){
si2=max(si2,int(r[i].se.size())*2-1);
}
}
int k=max(si,si2);
vector<vector<int>> ans(k,vector<int>(k));
for(int i=0; i<si; i++){
if(r[i].fi==0){
int c=r[i].se[0];
for(int j=0; j<k; j++) ans[i][j]=c;
continue;
}
int sk=r[i].se.size();
for(int j=0; j<sk; j++){
ans[i][j*2]=r[i].se[j];
if(j==sk-1) continue;
ans[i][j*2+1]=ans[i-1][0];
}
for(int j=sk*2-1; j<k; j++) ans[i][j]=ans[i][j-1];
}
for(int i=si; i<k; i++){
for(int j=0; j<k; j++){
ans[i][j]=ans[i-1][j];
}
}
return ans;
}
