#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fv3/Desktop/prog/debug/debug.h"
#else
#define debug(...) 42
#endif
int n, m;
mt19937 mt(time(0));
optional<vector<vector<int>>> solve(vector<vector<int>>& adj) {
vector<int> col;
vector<int> vis(n), last(n);
vector<vector<int>> pos(n);
int rem = n;
auto Dfs = [&](auto&& self, int i) -> void {
if (!rem) return;
pos[i].push_back(col.size());
col.push_back(i);
if (!vis[i]) {
vis[i] = 1;
rem--;
if (!rem) return;
}
for (auto node : adj[i]) if (node != last[i] && !vis[node]) {
last[node] = i;
self(self, node);
return;
}
if (last[i]) {
self(self, last[i]);
}
};
for (auto &list : adj) {
shuffle(list.begin(), list.end(), mt);
}
Dfs(Dfs, mt() % n);
assert(!rem);
set<int> extra;
for (int i = 0; i < n; i++) {
extra.insert(pos[i][mt() % pos[i].size()]);
}
int lines = col.size() + 2*n;
int K = 2 * n;
vector<vector<pair<int, int>>> diags(2 * K - 1);
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
diags[K-1 + i - j].push_back({i, j});
}
}
vector<set<int>> radj(n);
for (int i = 0; i < n; i++) {
for (auto node : adj[i]) {
radj[i].insert(node);
}
}
for (int i = 0; i < int(col.size()) - 1; i++) {
if (radj[col[i]].count(col[i+1])) {
radj[col[i]].erase(col[i+1]);
}
if (radj[col[i+1]].count(col[i])) {
radj[col[i+1]].erase(col[i]);
}
}
int diag = (2*K - 1 - lines) / 2;
int sz = int(col.size());
vector<int> extra_index(n);
vector<vector<int>> ans(K, vector<int>(K, col[0] + 1));
for (int i = 0; i < sz; i++) {
for (auto [y, x] : diags[diag]) {
ans[y][x] = col[i] + 1;
}
diag++;
if (!extra.count(i)) continue;
extra_index[col[i]] = diag;
for (int _ = 0; _ < 2; _++) {
for (auto [y, x] : diags[diag]) {
ans[y][x] = col[i] + 1;
}
diag++;
}
}
debug(col);
while (diag < 2 * K - 1) {
for (auto [y, x] : diags[diag++]) {
ans[y][x] = col.back() + 1;
}
}
rem = n;
queue<int> que;
for (int c = 0; c < n; c++) {
if (diags[extra_index[c]].size() < radj[c].size()) continue;
que.push(c);
vis[c] = 1;
rem--;
}
while (!que.empty()) {
int s = que.front();
que.pop();
int i = 0;
for (auto c : radj[s]) {
auto [y, x] = diags[s][i];
ans[y][x] = c + 1;
i++;
}
for (int c = 0; c < n; c++) {
if (vis[c] || !radj[c].count(s)) continue;
radj[c].erase(s);
if (diags[extra_index[c]].size() < radj[c].size()) continue;
que.push(c);
vis[c] = 1;
rem--;
}
for (int c = 0; c < n; c++) {
if (vis[c] || diags[extra_index[c]].size() < radj[c].size()) continue;
que.push(c);
vis[c] = 1;
rem--;
}
}
if (rem) return {};
return ans;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
n = N; m = M;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
A[i]--; B[i]--;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
auto ans = solve(adj);
while (!ans) ans = solve(adj);
return *ans;
}
