#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 42;
vector<pair<int, int>> ord;
vector<int> adj[mxN];
int par[mxN];
void dfs(int u, int par){
if(par > 0) ord.push_back({u, par});
for(auto it : adj[u]){
if(it ^ par) dfs(it, u);
}
if(par > 0) ord.push_back({par, u});
}
int find(int u){
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
bool unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return 0;
par[u] = v; return 1;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
for(int i = 1; i <= N; ++i){
par[i] = i;
}
for(int i = 0; i < M; ++i){
if(unite(A[i], B[i])){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
dfs(1, 0);
vector<vector<int>> ans(max(1, (int) ord.size()), vector<int>(max(1, (int) ord.size()), 1));
//cout << ord.size() << "\n";
for(int i = 0; i < ord.size(); ++i){
ans[i][0] = ord[i].first;
ans[i][1] = ord[i].second;
for(int j = 2; j < ord.size(); ++j) ans[i][j] = ans[i][j - 1];
}
for(int i = 1; i <= N; ++i) adj[i].clear();
ord.clear();
return ans;
}
