#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) {
vector <int> temp_id(N + 1);
iota(temp_id.begin(), temp_id.end(), 0);
vector <vector <int>> connected(N + 1, vector <int> (N + 1));
vector <vector <int>> dsu_graph(N + 1);
for (int i = 0; i < M; ++i) {
connected[A[i]][B[i]] = connected[B[i]][A[i]] = true;
int u = temp_id[A[i]], v = temp_id[B[i]];
if (u == v) continue;
dsu_graph[A[i]].push_back(B[i]);
dsu_graph[B[i]].push_back(A[i]);
for (int p = 1; p <= N; ++p) {
if (temp_id[p] == v) temp_id[p] = u;
}
}
vector <vector <int>> finale;
auto DFS = [&] (auto DFS, int u) -> void {
finale.emplace_back();
for (int i = 1; i <= N; ++i) {
if (connected[u][i] == false) continue;
finale.back().push_back(u);
finale.back().push_back(i);
}
finale.emplace_back();
finale.back().push_back(u);
for (int v : dsu_graph[u]) {
dsu_graph[v].erase(find(dsu_graph[v].begin(), dsu_graph[v].end(), u));
finale.emplace_back();
finale.back().push_back(v);
DFS(DFS, v);
finale.emplace_back();
finale.back().push_back(u);
}
};
DFS(DFS, 1);
int K = (int) finale.size();
for (vector <int>& F : finale) {
while ((int) F.size() < K) F.push_back(F[0]);
}
return finale;
}
