#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> visited;
vector<int> ret;
vector<vector<int>> graf, extras;
bool dfs(int curr, int depth) {
if (visited[curr]) return false;
visited[curr] = depth;
for (int i = 0; i < graf[curr].size(); ++i) {
ret.push_back(curr+1);
if (visited[graf[curr][i]] > depth) {
extras[curr].push_back(graf[curr][i]+1);
}
if (visited[graf[curr][i]]) continue;
dfs(graf[curr][i], depth + 1);
}
ret.push_back(curr+1);
return true;
}
std::vector<std::vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
ret.clear();
visited.assign(N, 0);
graf.assign(N, vector<int>{});
extras.assign(N, vector<int>{});
for (int i = 0; i < M; ++i) {
graf[A[i]-1].push_back(B[i] - 1);
graf[B[i]-1].push_back(A[i] - 1);
}
// cout<<"E"<<endl;
dfs(0, 1);
// cout<<"S"<<ret.size()<<endl;
vector<bool> exists(N+1, false);
vector<vector<int>> ans;
int len = ret.size() + 2 * N;
for (int i = 0; i < ret.size(); ++i) {
// if (i > 0 && ret[i] == ret[i-1]) continue;
if (exists[ret[i]]) {
ans.push_back(vector<int>(len, ret[i]));
continue;
}
exists[ret[i]] = true;
for (int j = 0; j <= 2; ++j) {
// cout<<(3 * i + j)<<endl;
ans.push_back(vector<int>(len, ret[i]));
if (j == 1) {
for (int k = 0; k < extras[ret[i]-1].size(); ++k) {
ans[ans.size()-1][2*k] = extras[ret[i]-1][k];
}
}
}
}
return ans;
}
