#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
bool visited[40];
vector<int>et;
vector<vector<int>>adj;
void dfs(int x){
et.push_back(x);
for(int i:adj[x]){
if(visited[i])continue;
visited[i]=true;
dfs(i);
et.push_back(x);
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
if(N==1)return {{1}};
vector<vector<int>>ans(2*N,vector<int>(2*N,1));
for(int i=0;i<N;i++)visited[i]=false;
et.clear();
adj.resize(N);
for(int i=0;i<N;i++)adj[i].clear();
vector<vector<bool>>adjm(N,vector<bool>(N,false));
for(int i=0;i<M;i++){
adj[A[i]-1].push_back(B[i]-1);
adj[B[i]-1].push_back(A[i]-1);
adjm[A[i]-1][B[i]-1]=true;
adjm[B[i]-1][A[i]-1]=true;
}
visited[0]=true;
dfs(0);
vector<vector<pair<int,int>>>diag(4*N);
for(int i=0;i<2*N;i++){
for(int j=0;j<2*N;j++){
diag[i+j].push_back({i,j});
}
}
for(int i=0;i<N;i++)visited[i]=false;
for(int i=0;i<2*N-2;i++){
adjm[et[i]][et[i+1]]=false;
adjm[et[i+1]][et[i]]=false;
}
int i=1;
vector<array<int,3>>d;
for(int j=1;j<2*N-1;j++){
while(!diag[i].empty()){
ans[diag[i].back().first][diag[i].back().second]=et[j]+1;
diag[i].pop_back();
}
i++;
if(visited[et[j]])continue;
visited[et[j]]=true;
d.push_back({min(i,4*N-1-i),i,et[j]});
i++;
while(!diag[i].empty()){
ans[diag[i].back().first][diag[i].back().second]=et[j]+1;
diag[i].pop_back();
}
i++;
}
sort(d.begin(),d.end());
for(int i=0;i<N;i++){
for(int j=0;j<i;j++){
if(adjm[d[i][2]][d[j][2]]){
ans[diag[d[i][1]].back().first][diag[d[i][1]].back().second]=d[j][2]+1;
diag[d[i][1]].pop_back();
}
}
while(!diag[d[i][1]].empty()){
ans[diag[d[i][1]].back().first][diag[d[i][1]].back().second]=d[i][2]+1;
diag[d[i][1]].pop_back();
}
}
return ans;
}
