#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 42;
vector<pair<int, int>> ord;
vector<int> adj[mxN];
bool vis[mxN];
void dfs(int u, int par){
if(par > 0) ord.push_back({u, par});
vis[u] = 1;
for(auto it : adj[u]){
if(it ^ par){
if(!vis[it]){
dfs(it, u);
}
}
}
if(par > 0) ord.push_back({par, u});
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
if(N == 1){
return {{1}};
}
for(int i = 1; i <= N; ++i) vis[i] = 0;
for(int i = 0; i < M; ++i){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 0);
vector<vector<int>> demo(max(1, (int) ord.size()), vector<int>(max(1, (int) ord.size()), 1));
vector<vector<int>> ans;
for(int i = 0; i < ord.size(); ++i){
demo[i][0] = ord[i].first;
demo[i][1] = ord[i].second;
for(int j = 2; j < ord.size(); ++j) demo[i][j] = demo[i][0];
}
for(int i = 0; i < (int) demo.size(); ++i){
ans.push_back(demo[i]);
vector<int> layer((int) demo.size());
int sz = 0;
for(int j = 0; j < (int) demo.size(); ++j){
if(sz >= adj[demo[i][0]].size()){
layer[j] = demo[i][1];
}else if(j == 1){
layer[j] = demo[i][0];
}else{
layer[j] = adj[demo[i][0]][sz++];
}
}
ans.push_back(layer);
ans.push_back(demo[i]);
}
for(int i = 1; i <= N; ++i) adj[i].clear(), vis[i] = 0;
ord.clear();
for(int i = 0; i < ans.size(); ++i){
while(ans[i].size() < ans.size()){
ans[i].push_back(ans[i].back());
}
}
for(int i = 0 ; i < ans.size(); ++i){
assert(ans.size() == ans[i].size());
}
assert(ans.size() <= 240);
return ans;
}
