#include "worldmap.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
vector<vector<int>> adj(N + 1);
vector<vector<int>> c(N + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
c[A[i]][B[i]] = c[B[i]][A[i]] = 1;
}
auto nc = c;
vector<vector<int>> now;
int mx = 0;
auto dfs = [&](auto& dfs, int v) -> void {
// cerr << "v=" << v << endl;
vector<int> left;
for (auto& u : adj[v]) {
if (c[v][u]) {
left.push_back(u);
c[v][u] = c[u][v] = 0;
}
}
if (sz(left) == 0) return;
now.push_back({v});
vector<int> add;
add.push_back(v);
for (auto& u : left) {
add.push_back(u);
add.push_back(v);
}
mx = max(mx, sz(add));
now.emplace_back(add);
now.push_back({v});
for (auto& u : left) {
// cerr << "v="<<v << "u=" << u << endl;
dfs(dfs, u);
}
};
dfs(dfs, 1);
if (N == 1) return {{1}};
// cerr << "a\n";
// cerr << sz(now) << endl;
mx = max(mx, sz(now));
vector<vector<int>> ret(mx);
for (int i = 0; i < sz(now); ++i) {
for (int j = 0; j < sz(now[i]); ++j) {
ret[i].push_back(now[i][j]);
}
for (int j = sz(now[i]); j < mx; ++j) {
ret[i].push_back(now[i][0]);
}
}
assert(sz(ret) == mx);
for (int i = 0; i < sz(ret); ++i) {
assert(sz(ret[i]) == mx);
}
// return ret;
for (int i = 0; i < mx; ++i) {
assert(sz(ret[i]) == mx);
for (int j = 0; j < mx; ++j) {
assert(ret[i][j] > 0);
assert(ret[i][j] <= N);
}
}
vector<vector<int>> a(N + 1, vector<int>(N + 1));
for (int i = 0; i < mx; ++i) {
for (int j = 0; j < mx; ++j) {
int A = ret[i][j];
if (i + 1 < mx) {
int B = ret[i + 1][j];
if (A != B) a[A][B] = a[B][A] = 1;
}
if (j + 1 < mx) {
int B = ret[i][j + 1];
if (A != B) a[A][B] = a[B][A] = 1;
}
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cerr << a[i][j];
}
cerr << endl;
}
cerr<<endl;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cerr << nc[i][j];
}
cerr << endl;
}
cerr<<endl;
assert(a == nc);
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
assert(c[i][j] == 0);
}
}
return ret;
}
