#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) {
if (n == 1) {
return {{1}};
}
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++) {
g[a[i]].push_back(make_pair(b[i], i));
g[b[i]].push_back(make_pair(a[i], i));
}
vector<bool> vis(n + 1);
vector<int> depth(n + 1);
vector<bool> done(m);
auto Dfs = [&](auto&& self, int v) -> void {
vis[v] = true;
for (auto [u, w] : g[v]) {
if (!vis[u]) {
done[w] = true;
depth[u] = depth[v] + 1;
self(self, u);
}
}
};
Dfs(Dfs, 1);
vector<bool> intree = done;
vector<vector<int>> ans;
auto Generate = [&](auto&& self, int v, int pr) -> void {
for (auto [u, w] : g[v]) {
if (u != pr && intree[w]) {
ans.push_back(vector<int>(4 * n, u));
done[w] = true;
self(self, u, v);
ans.push_back(vector<int>(4 * n, v));
}
}
vector<int> pb(4 * n);
int j = 0;
for (auto [u, w] : g[v]) {
if (!done[w]) {
pb[j] = u;
j++;
pb[j] = v;
j++;
done[w] = true;
}
}
while (j < 4 * n) {
pb[j] = v;
j++;
}
ans.push_back(pb);
ans.push_back(vector<int>(4 * n, v));
};
Generate(Generate, 1, 0);
int pad = 4 * n - ans.size();
vector<int> o = ans.back();
for (int j = 0; j < pad; j++) {
ans.push_back(o);
}
return ans;
}
