#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 44;
int n,m;
vector<int> adj[N];
int vis[N];
vector<vector<int>> rec;
void dfs(int u,int p){
// cout << "u :" << u << "\n";
rec.push_back({u});
vis[u] = 1;
vector<int> vec; // back edges
for (int v : adj[u]){
if (v == p) continue;
if (vis[v] == 1)
vec.push_back(v);
if (vis[v] == 0){
dfs(v, u);
rec.push_back({u});
}
}
vis[u] = 2;
if (vec.empty()) return;
vector<int> vec1,vec2;
vec1 = vec2 = {u};
for (int v : vec){
vec1.push_back(v);
vec1.push_back(u);
vec2.push_back(u);
vec2.push_back(u);
}
rec.push_back(vec1);
rec.push_back(vec2);
}
vector<vector<int>> create_map(int N,int M,vector<int> A,vector<int> B) {
n = N, m = M;
for (int i=1; i<=n; i++){
adj[i].clear();
vis[i] = 0;
}
rec.clear();
for (int i=0; i<m; i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, -1);
int k = rec.size();
for (auto &vec : rec){
while (vec.size() < k)
vec.push_back(vec.back());
}
return rec;
}
