#include "worldmap.h"
#include <bits/stdc++.h>
#define ar array
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 50;
vector<int> g[N];
vector<int> ord;
bool vis[N];
set<ar<int,2> > e;
int dep[N];
void dfs(int x){
vis[x] = 1;
// cout<<x<<" ";
for(auto u: g[x]){
if(vis[u])continue;
ord.push_back(x);
dep[u] = dep[x] + 1;
e.erase({min(u, x), max(u, x)});
dfs(u);
}
ord.push_back(x);
}
std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> A, std::vector<int> B) {
for(int i = 1;i <= n;i++)g[i].clear(), vis[i] = 0;
e.clear();
ord.clear();
for(int i = 0;i < m;i++){
auto [a, b] = ar<int,2>{A[i], B[i]};
g[a].push_back(b);
g[b].push_back(a);
// cout<<a<<" "<<b<<endl;
e.insert({min(a, b), max(a, b)});
}
dfs(1);
// cout<<endl;
int k = 2 * n;
vector<vector<int> > ans(k, vector<int>(k, -1));
vector<int> f[n + 1];
for(auto [a, b]: e){
if(dep[a] < dep[b])swap(a, b);
f[a].push_back(b);
}
vector<ar<int,2>> D[2 * k -1];
for(int i = 0;i < k;i++){
for(int j = 0;j < k;j++)D[i + j].push_back({i, j});
}
// for(auto u: ord)cout<<u<<" ";
// cout<<endl;
// assert(0);
set<int> s;
int d = 0;
for(auto u: ord){
if(s.count(u)){
for(auto [a, b]: D[d])ans[a][b] = u;
d++;
continue;
}
s.insert(u);
for(auto [a, b]: D[d])ans[a][b] = u;
d++;
for(auto [a, b]: D[d])ans[a][b] = u;
// cout<<D[d].size()<<" "<<f[u].size()<<'\n';
for(int i = 0;i < f[u].size();i++){
auto [a, b] = D[d][i];
ans[a][b] = f[u][i];
}
d++;
for(auto [a, b]: D[d])ans[a][b] = u;
d++;
}
for(;d < 2 * k - 1;d++){
for(auto [a, b]: D[d])ans[a][b] = 1;
}
return ans;
}
