#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
bool vis[41], don[41];
vector<int> adj[41];
vector<pair<int, int>> ord;
int deg[41], jp[41], kp[41];
set<pair<int, int>> st;
void dfs(int u) {
vis[u] = 1;
int cnt = 0;
for (auto& v : adj[u]) {
if (!vis[v]) {
cnt++;
st.insert({u, v});
ord.push_back({u, 0});
dfs(v);
ord.push_back({u, 1});
}
}
if (!cnt) ord.push_back({u, 0});
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
for (int i = 0; i <= 40; i++) vis[i] = 0, adj[i].clear(), deg[i] = 0, jp[i] = 100, kp[i] = 0, don[i] = 0;
ord.clear();
st.clear();
for (int i = 0; i < M; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1);
std::vector<std::vector<int>> ans(2 * N, std::vector<int>(2 * N, 1));
int p = 0, cnt = 0, prv = 0;
for (auto& [x, y] : ord) {
if (!don[x]) {
don[x] = 1;
cnt++;
for (int i = p; i < p + 3; i++) {
for (int j = 0; j < 2 * N; j++) {
int k = i - j;
if (k >= 0 && k < 2 * N) {
ans[j][k] = x;
if (i == p + 1) deg[x]++, jp[x] = min(jp[x], j); kp[x] = max(kp[x], k);
}
}
}
p += 3;
} else if (prv != x) {
for (int j = 0; j < 2 * N; j++) {
int k = p - j;
if (k >= 0 && k < 2 * N) ans[j][k] = x;
}
p++;
}
prv = x;
}
for (int i = 0; i < M; i++) {
if (st.count({A[i], B[i]}) || st.count({B[i], A[i]})) continue;
if (deg[A[i]] < deg[B[i]]) swap(A[i], B[i]);
assert(deg[A[i]] >= 1);
deg[A[i]]--, ans[jp[A[i]]++][kp[A[i]]--] = B[i];
}
return ans;
}
