#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(begin(cnt) +1 ,end(cnt));
for (int i = 1; i <= N; ++i) {
if (cnt[i] == mx) {
r = i;
break;
}
}
}
vector<vector<int>> now;
auto dfs = [&](auto& dfs, int v) -> void {
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;
vector<int> add;
for (auto& u : left) {
add.push_back(u);
}
add.push_back(v);
now.emplace_back(add);
for (auto& u : left) {
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();
int C = N * 2;
if (*max_element(all(cnt)) == N - 1) {
vector<vector<int>> nnow;
for (int i = 0; i < sz(now); ++i) {
if (sz(now[i]) == 2 && now[i][0] == now[i][1]) continue;
nnow.push_back(now[i]);
}
now.swap(nnow);
vector<vector<int>> X(C, vector<int>(C));
assert((C-1)/2>=sz(now));
for (int i = 0; i < C; ++i) {
if (i % 2 == 1 || i / 2 >= sz(now)) {
for (int j = 0; j < C; ++j) {
X.at(i).at(j) = r;
}
} else {
int ptr = 0;
for (int j = 0; j < sz(now[i/2]); ++j){
X.at(i).at(ptr) = now[i/2][j];
ptr+=1;
X.at(i).at(ptr) = now[i/2].back();
ptr+=1;
}
for (int j = ptr; j < C; ++j) {
X.at(i).at(j) = r;
}
}
}
return X;
}
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) {
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]});
}
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);
}
}
}
return X;
}
