#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<pair<int, int>>> adj(N+1);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], i);
adj[B[i]].emplace_back(A[i], i);
}
vector<int> sigma;
vector<bool> vis(M);
auto dfs = [&](auto &&dfs, int u) -> void {
sigma.push_back(u);
for (auto &[v, id] : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
dfs(dfs, v);
sigma.push_back(u);
}
};
dfs(dfs, 1);
cerr << N sp sigma.size() << endl;
vector<int> rizzler, loc(N+1, 0);
vector<bool> vis2(N+1);
for (auto &x : sigma) {
if (vis2[x]) rizzler.emplace_back(x);
else {
vis2[x] = true;
rizzler.emplace_back(x);
loc[x] = rizzler.size();
rizzler.emplace_back(x);
rizzler.emplace_back(x);
}
}
cerr << N sp rizzler.size() << endl;
rizzler.pop_back();
int K = rizzler.size();
vector<vector<int>> ans(K, vector<int>(K));
for (int i = 0; i < K; i++) {
ans[i] = rizzler;
}
vector<vector<bool>> vis3(N+1, vector<bool>(N+1));
for (int i = 1; i <= N; i++) {
int j = loc[i], k = 0;
for (auto &[v, id] : adj[i]) {
if (vis3[i][v]) continue;
vis3[i][v] = true;
ans[k][j] = v;
k += 2;
}
}
return ans;
}
