#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
vector<vector<int>> graph(n+1);
for (int i = 0; i < m; i++) {
graph[a[i]].pb(b[i]);
graph[b[i]].pb(a[i]);
}
vector<int> ord;
vector<bool> used(n+1, false);
auto dfs = [&](auto &dfs, int u) -> void {
used[u] = true;
ord.pb(u);
for (int e : graph[u])
if (!used[e]) {
dfs(dfs, e);
ord.pb(u);
}
};
dfs(dfs, 1);
vector<int> v;
vector<bool> used1(n+1, false);
for (int e : ord) {
v.pb(e);
if (!used1[e]) {
v.pb(e);
v.pb(e);
}
used1[e] = true;
}
vector<vector<int>> ans(4*n, v);
for (int i = 1; i < v.size()-1; i++) {
if (ans[0][i-1] == ans[0][i+1] && ans[0][i-1] == ans[0][i]) {
stack<int> q;
for (int e : graph[ans[0][i]])
q.push(e);
for (int j = 0; j < 4*n && !q.empty(); j += 2) {
ans[j][i] = q.top();
q.pop();
}
}
}
for (auto &e : ans)
while (e.size() < 4*n)
e.pb(e.back());
return ans;
}
