#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
if (n == 1) {
return {{1}};
}
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < m; i++) {
g[a[i]].push_back(make_pair(b[i], i));
g[b[i]].push_back(make_pair(a[i], i));
}
vector<bool> vis(n + 1);
vector<int> depth(n + 1);
vector<bool> done(m);
auto Dfs = [&](auto&& self, int v) -> void {
vis[v] = true;
for (auto [u, w] : g[v]) {
if (!vis[u]) {
done[w] = true;
depth[u] = depth[v] + 1;
self(self, u);
}
}
};
Dfs(Dfs, 1);
vector<bool> intree = done;
vector<pair<int, int>> ord;
auto Generate = [&](auto&& self, int v, int pr) -> void {
for (auto [u, w] : g[v]) {
if (u != pr && intree[w]) {
ord.emplace_back(v, u);
done[w] = true;
self(self, u, v);
ord.emplace_back(u, v);
}
}
for (auto [u, w] : g[v]) {
if (!done[w]) {
ord.emplace_back(v, u);
done[w] = true;
ord.emplace_back(u, v);
}
}
};
Generate(Generate, 1, 0);
vector<vector<int>> ans(ord.size() + 1, vector<int>(ord.size() + 1));
for (int i = 0; i < ord.size(); i++) {
for (int j = 0; j <= ord.size(); j++) {
ans[i][j] = ord[i].first;
}
}
for (int i = 0; i <= ord.size(); i++) {
ans[ord.size()][i] = ord[ord.size() - 1].second;
}
return ans;
}
