#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,avai[45],cnt,pos[45];
vector<int> adj[45],ord;
bool vis[45];
void dfs(int x) {
vis[x]=true;
if (cnt!=n) ord.push_back(x);
++cnt;
for (auto s : adj[x]) {
if (vis[s]) continue;
dfs(s);
if (cnt!=n) ord.push_back(x);
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
n=N; m=M; cnt=0;
memset(avai,-1,sizeof(avai));
for (int i=1; i<=n; ++i) adj[i].clear();
ord.clear();
memset(vis,0,sizeof(vis));
vector<vector<int>> ans(2*n, vector<int>(2*n));
for (int i=0; i<2*n; ++i) for (int j=0; j<2*n; ++j) ans[i][j]=0;
for (int i=0; i<m; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1);
int idx=0;
for (int i=0; i<(int)(ord.size()); ++i) {
int city=ord[i];
for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ans[j][idx-j]=city;
++idx;
if (avai[city]==-1) {
avai[city]=0;
for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ++avai[city];
pos[city]=idx;
++idx;
for (int j=0; j<=idx; ++j) if (j<2*n && idx-j<2*n) ans[j][idx-j]=city;
++idx;
}
}
for (int i=idx; i<4*n-1; ++i) for (int j=0; j<=i; ++j) if (j<2*n && i-j<2*n) ans[j][i-j]=ord.back();
vector<int> v;
for (int i=1; i<=n; ++i) v.push_back(i);
sort(v.begin(), v.end(), [](int a, int b){
return avai[a]<avai[b];
});
int rnk[n+5];
for (int i=0; i<n; ++i) rnk[v[i]]=i;
for (int i=1; i<=n; ++i) {
vector<int> temp;
for (auto s : adj[i]) if (rnk[s]<rnk[i]) temp.push_back(s);
int idx=0;
for (int j=0; j<=pos[i]; ++j) {
if (j<2*n && pos[i]-j<2*n) {
if (idx==temp.size()) ans[j][pos[i]-j]=i;
else ans[j][pos[i]-j]=temp[idx++];
}
}
}
return ans;
}
