#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const ll NAIM = 9e18;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
ll n = N, m = M;
ll lo = 1, hi = 240;
vector<vector<int>> res;
ll sz = NAIM;
while(lo <= hi) {
vector<set<ll>> g(n + 1);
FOR(i, 0, m) {
ll u = A[i], v = B[i];
g[u].insert(v);
g[v].insert(u);
}
ll k = (lo + hi) / 2;
vector<vector<int>> cur(k, vector<int> (k, 0));
pair<ll, ll> last = {0, 0};
auto ok = [&](ll x, ll y) {
return 0 <= x && x < k && 0 <= y && y < k;
};
function<void(ll, ll, ll, ll, ll)> dfs = [&](ll country, ll x, ll y, ll now, ll state) {
if(state == 0) cur[x][y] = country;
else cur[x][y] = now;
ll x1 = x + 1, y1 = y - 1;
if(ok(x1, y1)){
if(state == 1){
if(g[country].empty()) dfs(country, x1, y1, country, 1);
else {
auto it = g[country].begin();
ll to = *it;
g[country].erase(it);
g[to].erase(country);
dfs(country, x1, y1, to, 1);
}
}
else dfs(country, x1, y1, country, 0);
}
else{
if(last.ss < k - 1) last.ss++;
else last.ff++;
if(ok(last.ff, last.ss) == false) return;
if(state == 0) {
if(g[country].empty()) return;
else {
auto it = g[country].begin();
ll to = *it;
g[country].erase(it);
g[to].erase(country);
dfs(country, last.ff, last.ss, to, 1);
}
}
else dfs(country, last.ff, last.ss, country, 0);
}
};
FOR(country, 1, n + 1) {
if(ok(last.ff, last.ss)) {
dfs(country, last.ff, last.ss, country, 0);
}
}
FOR(i, 0, k) {
FOR(j, 0, k) {
if(cur[i][j] == 0) {
if(i == 0 && j == 0) continue;
if(i > 0 && cur[i - 1][j] != 0) cur[i][j] = cur[i - 1][j];
else if(j > 0 && cur[i][j - 1] != 0) cur[i][j] = cur[i][j - 1];
}
}
}
bool flag = 1;
FOR(i, 1, n + 1) if(!g[i].empty()) flag = 0;
if(flag) {
hi = k - 1;
if(k < sz) {
sz = k;
res = cur;
}
}
else {
lo = k + 1;
}
}
return res;
}
