#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);
vector<vector<bool>> con(n+1, vector<bool> (n+1, false)), legal(n+1, vector<bool> (n+1, false));
for (int i = 0; i < m; i++) {
legal[a[i]][b[i]] = true;
legal[b[i]][a[i]] = true;
}
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);
for (int i = 0; i < ord.size()-1; i++) {
con[ord[i]][ord[i+1]] = true;
con[ord[i+1]][ord[i]] = true;
}
vector<int> v;
vector<bool> used1(n+1, false);
for (int e : ord) {
v.pb(e);
if (!used1[e]) {
v.pb(e);
}
used1[e] = true;
}
vector<vector<int>> ans(3*n, v);
for (int i = 0; i < v.size()-1; i++) {
if (ans[0][i] != ans[0][i+1])
continue;
int st = 2;
if (i&2)
st = 1;
stack<int> q;
for (int e : graph[ans[0][i]])
if (!con[e][ans[0][i]])
q.push(e);
for (int j = st; j < ans.size() && !q.empty(); j+=2) {
if (i > 0) {
if (!legal[ans[j][i-2]][ans[j][i]])
continue;
ans[j][i-1] = ans[j][i];
}
con[ans[0][i]][q.top()] = true;
con[q.top()][ans[0][i]] = true;
ans[j][i] = q.top();
q.pop();
}
}
for (auto &e : ans)
while (e.size() < 3*n)
e.pb(e.back());
return ans;
}
