#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 42;
vector<int> adj[mxN], waiting[mxN];
vector<pair<int, int>> ord;
int parent[mxN];
int find(int u){
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
bool unite(int u, int v){
u = find(u), v = find(v);
if(u == v) return 0;
return parent[u] = v;
}
void dfs(int u = 1, int par = 0){
if(par) ord.push_back({u, par});
for(auto it : adj[u]){
if(it ^ par) dfs(it, u);
}
if(par) ord.push_back({par, u});
}
void reset(int N){
ord.clear();
for(int i = 1; i <= N; ++i){
adj[i].clear();
waiting[i].clear();
parent[i] = i;
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
reset(N);
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]);
}else{
waiting[A[i]].push_back(B[i]);
}
}
dfs(1, 0);
vector<vector<int>> ans;
for(int i = 0; i < ord.size(); ++i){
vector<int> top_layer = {ord[i].first, ord[i].second};
vector<int> mid_layer;
for(auto it : waiting[ord[i].first]){
if(mid_layer.size() == 1) mid_layer.push_back(ord[i].first);
mid_layer.push_back(it);
}
ans.push_back(top_layer);
if(mid_layer.size()) ans.push_back(mid_layer);
ans.push_back(top_layer);
}
for(int i = 0; i < (int) ans.size(); ++i){
while((int) ans.size() > (int) ans[i].size()) ans[i].push_back(ans[i][0]);
}
return ans;
}
