#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
vector<vector<int>> adj(n+1), ans;
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<int> order = {1}, vis(n+1, false);
auto dfs = [&](int node, auto& dfs) -> void {
vis[node] = 1;
order.push_back(node);
for (int u : adj[node]) if (!vis[u]) {
dfs(u, dfs);
order.push_back(node);
}
};
dfs(1, dfs);
fill(vis.begin(), vis.end(), 0);
for (int node : order) {
ans.push_back({node});
if (!vis[node]) {
vis[node] = true;
vector<int> lay = {node};
for (int u : adj[node]) {
lay.push_back(u);
lay.push_back(node);
}
ans.push_back(lay);
ans.push_back({node});
}
}
int sz = ans.size();
for (auto& v : ans) while (v.size() < sz) v.push_back(v.back());
return ans;
}
