#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
int was[45];
vector < int > ans;
vector < int > g[45], reb[45];
void dfs(int v, int p){
was[v] = 1, ans.push_back(v);
for(int u : g[v]){
if(u == p) continue;
if(!was[u]) dfs(u, v);
else reb[v].push_back(u);
}
if(v > 1) ans.push_back(p);
}
vector < vector < int > > create_map(int n, int m, vector < int > a, vector< int > b) {
ans.clear();
for(int i = 0; i <= n; i++) g[i].clear(), reb[i].clear(), was[i] = 0;
for(int i = 0; i < m; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs(1, 1);
int id = 0;
for(int i = 0; i <= n; i++) was[i] = 0;
vector < vector < int > > ret((4 * n), vector < int > (4 * n));
for(int i = 0; i < 4 * n; i++){
if(id == ans.size()){
for(int j = 0; j < 4 * n; j++) ret[i][j] = ret[i - 1][j];
continue;
}
if(!was[ans[id]]){
for(int j = 0; j < 4 * n; j++) ret[i][j] = ret[i + 1][j] = ret[i + 2][j] = ans[id];
for(int j = 0; j < 4 * n; j += 2){
if(reb[ans[id]].empty()) break;
ret[i + 1][j] = reb[ans[id]].back();
reb[ans[id]].pop_back();
}
was[ans[id]] = 1, i += 2, id++;
}
else{
for(int j = 0; j < 4 * n; j++) ret[i][j] = ans[id];
id++;
}
}
return ret;
}
