#include "worldmap.h"
#include <assert.h>
std::vector<int> adj[45];
std::vector<int> ord;
int ans[95][95];
bool seen[45];
void dfs(int at) {
seen[at] = true;
ord.push_back(at);
for (int u : adj[at]) {
if (!seen[u]) {
dfs(u);
ord.push_back(at);
}
}
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
for (int i = 0; i < n; i++)
adj[i].clear();
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);
}
ord.clear();
for (int i = 0; i < n; i++)
seen[i] = false;
dfs(0);
for (int i = 0; i < 2 * n; i++)
for (int j = 0; j < 2 * n; j++)
ans[i][j] = ord.back();
for (int i = 0; i < n; i++)
seen[i] = false;
int diag = 0;
for (int u : ord) {
for (int i = 0; i < 4 * n; i++) {
int r = i, c = diag - i;
if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n)
ans[r][c] = u;
}
diag++;
if (seen[u]) {
continue;
}
seen[u] = true;
std::vector<int> here;
for (int v : adj[u])
if (seen[v])
here.push_back(v);
for (int i = 0; i < 4 * n; i++) {
int r = i, c = diag - i;
if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n) {
if (here.empty())
ans[r][c] = u;
else {
ans[r][c] = here.back();
here.pop_back();
}
}
}
diag++;
assert(here.empty());
for (int i = 0; i < 4 * n; i++) {
int r = i, c = diag - i;
if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n)
ans[r][c] = u;
}
diag++;
}
std::vector<std::vector<int>> result;
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++)
ans[i][j]++;
result.emplace_back(ans[i], ans[i] + 2 * n);
}
return result;
}
