#include "worldmap.h"
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
const int K = 2 * N;
vector<vector<int>> ans(K, vector<int>(K, 0));
vector<vector<int>> adj(N);
vector<vector<bool>> used(K, vector<bool>(K, false));
vector<pair<int, int>> pos(N, {-1, -1});
for (int i = 0; i < M; ++i) {
int u = A[i] - 1;
int v = B[i] - 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
queue<int> q;
q.push(0);
pos[0] = {K / 2, K / 2};
ans[K / 2][K / 2] = 1;
used[K / 2][K / 2] = true;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
while (!q.empty()) {
int u = q.front(); q.pop();
auto [x, y] = pos[u];
for (int v : adj[u]) {
if (pos[v].first != -1) continue;
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || ny < 0 || nx >= K || ny >= K) continue;
if (used[nx][ny]) continue;
pos[v] = {nx, ny};
ans[nx][ny] = v + 1;
used[nx][ny] = true;
q.push(v);
break;
}
}
}
for (int i = 0; i < N; ++i) {
if (pos[i].first != -1) continue;
for (int x = 0; x < K; ++x) {
for (int y = 0; y < K; ++y) {
if (!used[x][y]) {
ans[x][y] = i + 1;
used[x][y] = true;
pos[i] = {x, y};
goto next;
}
}
}
next:;
}
return ans;
}
