#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int> > adj;
vector <bool> visited;
vector <int> ord;
void dfs(int v) {
visited[v]=true;
ord.push_back(v);
for (auto u: adj[v]) {
if (!visited[u]) {
dfs(u);
ord.push_back(v);
}
}
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
ord.clear();
adj = vector <vector <int> > (n+1);
visited=vector <bool> (n+1);
//cout << "here" << endl;
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
vector <vector <int> > ans;
dfs(1);
//cout << "order size is " << ord.size() << endl;
vector <int> seen(n+1);
for (int i = 0; i < ord.size(); i++) {
//cout << ord[i] << " ";
if (!seen[ord[i]]) {
vector <int> v;
for (int j = 0; j < 2*n+2; j++) {
v.push_back(ord[i]);
}
ans.push_back(v);
vector <int> sec;
for (auto u: adj[ord[i]]) {
sec.push_back(ord[i]);
sec.push_back(u);
}
sec.push_back(ord[i]);
ans.push_back(sec);
ans.push_back(v);
seen[ord[i]]=true;
} else {
vector <int> v;
for (int j = 0; j < 2*n+2; j++) {
v.push_back(ord[i]);
}
ans.push_back(v);
}
}
int k = 4*n-1;
for (int i = 0; i < ans.size(); i++) {
//cout << i << " " << ans[i].size() << endl;
int x= (int)ans[i].size();
for (int j = 0; j < k-x; j++) {
//cout << "going through " << i << endl;
ans[i].push_back(ans[i][0]);
}
}
int x = ans[ans.size()-1][0];
vector <int> v;
for (int i = 0; i < k; i++) {
v.push_back(x);
}
int c = (int)ans.size();
for (int i = 0; i <k-c; i++) {
ans.push_back(v);
}
//cout << endl;
//cout << "here" << endl;
return ans;
}
