#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const int MAX_N = 40;
vi adj[MAX_N];
bool vis[MAX_N];
set<ii> pending;
vi euler;
void dfs(int u) {
vis[u] = true;
euler.pb(u);
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
pending.erase(minmax(u, v));
euler.pb(u);
}
}
}
vector<vi> create_map(int N, int M, vi A, vi B) {
forn(i, MAX_N) adj[i].clear(), vis[i] = false;
pending.clear(), euler.clear();
forn(i, M) {
A[i]--, B[i]--;
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
pending.emplace(minmax(A[i], B[i]));
}
dfs(0);
forn(i, N) vis[i] = false;
const int K = 2 * N;
vector<vi> ret(K, vi(K));
vector<vector<ii>> diag(2 * K);
forn(i, K) forn(j, K) {
diag[i + j].eb(i, j);
}
vector<ii> toAdd;
int d = 0;
for (int u : euler) {
for (auto [i, j] : diag[d]) {
ret[i][j] = u;
}
d++;
if (!vis[u]) {
toAdd.eb(d, u);
d++;
for (auto [i, j] : diag[d]) {
ret[i][j] = u;
}
d++;
vis[u] = true;
}
}
while (d < 2 * K) {
for (auto [i, j] : diag[d]) {
ret[i][j] = euler.back();
}
d++;
}
sort(all(toAdd), [&](const auto &lhs, const auto &rhs) {
return sz(diag[lhs.fst]) > sz(diag[rhs.fst]);
});
for (auto [d, u] : toAdd) {
int idx = 0;
for (int v : adj[u]) if (idx < sz(diag[d]) && pending.count(minmax(u, v))) {
auto [i, j] = diag[d][idx++];
ret[i][j] = v;
pending.erase(minmax(u, v));
}
while (idx < sz(diag[d])) {
auto [i, j] = diag[d][idx++];
ret[i][j] = u;
}
}
forn(i, K) forn(j, K) ret[i][j]++;
return ret;
}
