#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 40 + 11;
vector<int> G[N_MAX];
vector<vector<int>> regulate(vector<vector<int>> board) {
int n = board.size(), m = board[0].size();
int K = max(n, m);
vector ans = vector(K, vector<int>(K));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = board[i][j];
}
}
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
if (!ans[i][j]) {
if (j > 0 && ans[i][j - 1]) ans[i][j] = ans[i][j - 1];
else if (i > 0 && ans[i - 1][j]) ans[i][j] = ans[i - 1][j];
else assert(false);
}
}
}
// for (int i = 0; i < K; i++) {
// for (int j = 0; j < K; j++) {
// cout << ans[i][j] << ' ';
// }
// cout << '\n';
// }
return ans;
}
bool vis[N_MAX];
vector<pair<int, bool>> st;
void dfs(int v, int pa = -1) {
vis[v] = true;
for (int u : G[v]) {
if (vis[u]) continue;
st.push_back({u, true});
dfs(u, v);
st.push_back({v, false});
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
for (int i = 1; i <= N; i++) {
G[i].clear();
}
fill(vis, vis + N + 1, false);
for (int i = 0; i < M; i++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
st = vector<pair<int, bool>>{{1, true}}; dfs(1);
vector ans = vector(N * 3 + (N - 1), vector<int> (N * 2));
int x = 0;
for (auto [v, fi] : st) {
if (fi) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < N * 2; k++) {
ans[x + j][k] = v;
}
}
for (int j = 0; j < G[v].size(); j++) {
ans[x + 1][j * 2] = G[v][j];
}
x += 3;
} else {
for (int k = 0; k < N * 2; k++) {
ans[x][k] = v;
}
x++;
}
}
return regulate(ans);
}
