#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; }