#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]] && !legal[ans[j][i-1]][q.top()]) continue; else if (!legal[ans[j][i-2]][ans[j][i]]) 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; }