#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;
int e[N][N];
int s[N];
vector<int> r;
vector<int> f[N];
int pa[N];
int n;
void dfs(int v, int p, int dz){
r.pb(v);
s[v]=1;
pa[v]=p;
for(int i=0; i<2*(n-dz); i++) f[v].pb(v);
for(int i=2*(n-dz); i<2*n; i++) f[v].pb(f[p][i]);
for(int i=1; i<=n; i++){
if(i==v || s[i]) continue;
if(e[v][i]){
dfs(i,v,dz+1);
r.pb(v);
}
}
return;
}
vector<vector<int>> create_map(int nn, int m, vector<int> a, vector<int> b){
n=nn;
r.clear();
for(int i=1; i<=n; i++){
s[i]=0;
for(int j=1; j<=n; j++) e[i][j]=0;
f[i].clear();
}
for(int i=0; i<m; i++){
e[a[i]][b[i]]=1;
e[b[i]][a[i]]=1;
}
dfs(1,1,0);
for(int v=1; v<=n; v++){
for(int i=1; i<2*n; i+=2){
if(f[v][i]==v || f[v][i]==pa[v]) continue;
if(e[v][f[v][i]]){
f[v][i]=v;
if(i!=2*n-1){
if(!e[v][f[v][i+2]]){
f[v][i+1]=f[v][i-1];
}
}
}
}
}
vector<vector<int>> ans(2*n,vector<int>(2*n));
for(int i=0; i<r.size(); i++){
for(int j=0; j<2*n; j++){
ans[i][j]=f[r[i]][j];
}
}
for(int i=r.size(); i<2*n; i++){
for(int j=0; j<2*n; j++) ans[i][j]=1;
}
return ans;
}
