#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)); 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) ans[j][i-1] = ans[j][i]; ans[j][i] = q.top(); q.pop(); } } for (auto &e : ans) while (e.size() < 3*n) e.pb(e.back()); return ans; }