#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 sz = NAIM;
ll k = 2 * n;
vector<set<ll>> g(n + 1);
vector<vector<ll>> g1(n + 1);
FOR(i, 0, m) {
ll u = A[i], v = B[i];
g[u].insert(v);
g[v].insert(u);
g1[u].pb(v);
g1[v].pb(u);
}
vector<vector<int>> res(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;
};
ll last_country = 1;
function<void(ll, ll, ll, ll, ll)> dfs = [&](ll country, ll x, ll y, ll now, ll state) {
last_country = country;
if(state == 0) res[x][y] = country;
else res[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);
}
};
vector<ll> walk;
vector<bool> vis(n + 1, 0);
function<void(ll)> dfs1 = [&](ll u) {
vis[u] = 1;
walk.pb(u);
for(auto &v : g1[u]) {
if(!vis[v]) {
dfs1(v);
walk.pb(u);
}
}
};
FOR(i, 1, n + 1) {
if(!vis[i]) {
dfs1(i);
break;
}
}
for(auto &x : walk) {
if(ok(last.ff, last.ss) == false) break;
dfs(x, last.ff, last.ss, x, 0);
}
FOR(i, 0, k) {
FOR(j, 0, k) {
if(res[i][j] == 0) {
res[i][j] = last_country;
}
}
}
return res;
}
