#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));
vector<int> cnt(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
cnt[A[i]] += 1;
cnt[B[i]] += 1;
c[A[i]][B[i]] = c[B[i]][A[i]] = 1;
}
int r = -1;
{
int mx = *max_element(all(cnt));
for (int i = 1; i <= N; ++i) {
if (cnt[i] == mx) {
r = i;
break;
}
}
}
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);
}
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);
if (now.back().back() != v) now.push_back({v, v});
}
};
dfs(dfs, r);
if (N == 1) return {{1}};
while (sz(now) && sz(now.back()) == 2 && now.back()[0] == now.back()[1]) now.pop_back();
// sort(all(now), [&](auto& x, auto& y) {
// return sz(x) > sz(y);
// });
int C = 2 * N;
vector<vector<int>> X(C, vector<int>(C));
int si = C - 1, sj = C - 1;
auto fill = [&](int i, int j, vector<int> v) -> void {
while (j >= 0 && X.at(i).at(j) != 0) j -= 1;
while (j >= 0 && min(C - j, i + 1) < sz(v) - 1) j -= 1;
if (j < 0) {
j = 0;
while (X.at(i).at(j) != 0) i -= 1;
while (min(C - j, i + 1) < sz(v) - 1) i -= 1;
}
si = i;
sj = j;
for (int it = 0; it + 1 < sz(v); ++it) {
X.at(i).at(j) = v[it];
i -= 1;
j += 1;
}
while (i >= 0 && j < C) {
X.at(i).at(j) = v[sz(v) - 1];
i -= 1;
j += 1;
}
};
for (auto& v : now) {
// for (int i = 0; i < C; ++i) {
// for (int j = 0; j < C; ++j) {
// cerr << X.at(i).at(j) << " ";
// }
// cerr << endl;
// }
// cerr << endl;
// dbg(v);
if (v[0] == v[sz(v) - 1]) {
fill(si, sj, {v[sz(v) - 1]});
continue;
}
fill(si, sj, {v[sz(v) - 1]});
fill(si, sj, v);
fill(si, sj, {v[sz(v) - 1]});
}
// cerr << "done!\n";
// cerr << "a\n";
// cerr << sz(now) << endl;
mx = C;
// cerr << "here!\n";
auto bfs = [&](int si, int sj) -> void {
int Z = X.at(si).at(sj);
queue<pair<int, int>> q;
q.push({si, sj});
vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
while (sz(q)) {
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni < 0 || nj < 0 || ni >= sz(X) || nj >= sz(X)) continue;
if (X[ni][nj] == 0) {
q.push({ni, nj});
X[ni][nj] = Z;
}
}
}
};
if (X.at(0).at(0) != 0) bfs(0, 0);
if (X.at(C - 1).at(C - 1) != 0) bfs(C - 1, C - 1);
for (int i = 0; i < C; ++i) {
for (int j = 0; j < C; ++j) {
if (X.at(i).at(j) != 0) {
bfs(i, j);
}
}
}
// cerr << "A\n";
// return ret;
// for (auto& v:ret){
// for (int i :v)cerr << i<< " ";
// cerr << endl;
// }
// assert(sz(ret) == mx);
// 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 = X.at(i).at(j);
if (i + 1 < mx) {
int B = X[i + 1][j];
if (A != B) a[A][B] = a[B][A] = 1;
}
if (j + 1 < mx) {
int B = X[i][j + 1];
if (A != B) a[A][B] = a[B][A] = 1;
}
}
}
// cerr << "B\n";
// 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;
// for (int i = 0; i < C; ++i) {
// for (int j = 0; j < C; ++j) {
// cerr << X.at(i).at(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);
// }
// }
// cerr << "C\n";
return X;
}
