/*
.----------------. .----------------. .----------------. .----------------. .----------------. .----------------. .----------------. .-----------------. .----------------. .----------------. .----------------. .----------------. .----------------. .----------------. .-----------------. .----------------. .----------------. .----------------. .----------------. .-----------------.
| .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. |
| | ____ ____ | || | _____ _____ | || | ____ ____ | || | _____ | || | _________ | || | _________ | | | | __ | || | ____ _____ | || | ________ | | | | _________ | || | _______ | || | _____ | || | _________ | || | _________ | || | ____ _____ | || | ______ | || | _____ _____ | || | _________ | || | ____ ____ | || | ____ _____ | |
| ||_ _| |_ _| | || ||_ _||_ _|| || ||_ _| |_ _| | || | |_ _| | || | |_ ___ | | || | | _ _ | | | | | / \ | || ||_ \|_ _| | || | |_ ___ `. | | | | | _ _ | | || | |_ __ \ | || | |_ _| | || | |_ ___ | | || | | _ _ | | || ||_ \|_ _| | || | .' ___ | | || ||_ _||_ _|| || | |_ ___ | | || | |_ _||_ _| | || ||_ \|_ _| | |
| | \ \ / / | || | | | | | | || | \ \ / / | || | | | | || | | |_ \_| | || | |_/ | | \_| | | | | / /\ \ | || | | \ | | | || | | | `. \ | | | | |_/ | | \_| | || | | |__) | | || | | | | || | | |_ \_| | || | |_/ | | \_| | || | | \ | | | || | / .' \_| | || | | | | | | || | | |_ \_| | || | \ \ / / | || | | \ | | | |
| | \ \ / / | || | | ' ' | | || | \ \ / / | || | | | | || | | _| _ | || | | | | | | | / ____ \ | || | | |\ \| | | || | | | | | | | | | | | | || | | __ / | || | | | | || | | _| _ | || | | | | || | | |\ \| | | || | | | ____ | || | | ' ' | | || | | _| _ | || | \ \/ / | || | | |\ \| | | |
| | \ ' / | || | \ `--' / | || | \ ' / | || | _| |_ | || | _| |___/ | | || | _| |_ | | | | _/ / \ \_ | || | _| |_\ |_ | || | _| |___.' / | | | | _| |_ | || | _| | \ \_ | || | _| |_ | || | _| |___/ | | || | _| |_ | || | _| |_\ |_ | || | \ `.___] _| | || | \ `--' / | || | _| |___/ | | || | _| |_ | || | _| |_\ |_ | |
| | \_/ | || | `.__.' | || | \_/ | || | |_____| | || | |_________| | || | |_____| | | | ||____| |____|| || ||_____|\____| | || | |________.' | | | | |_____| | || | |____| |___| | || | |_____| | || | |_________| | || | |_____| | || ||_____|\____| | || | `._____.' | || | `.__.' | || | |_________| | || | |______| | || ||_____|\____| | |
| | | || | | || | | || | | || | | || | | | | | | || | | || | | | | | | || | | || | | || | | || | | || | | || | | || | | || | | || | | || | | |
| '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' |
'----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------' '----------------'
*/
#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
void dfs(int u, vector<bool>& vis, vvi& adj, vi& tour) {
vis[u] = true;
tour.push_back(u);
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v, vis, adj, tour);
tour.push_back(u);
}
}
}
vvi create_map(int n, int m, vi a, vi b) {
vvi adj(n + 1);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
vector<bool> vis(n + 1, false);
vi tour;
dfs(1, vis, adj, tour);
const int K = 3 * n - 1;
vector<set<pair<int, int>>> diags(2 * K - 1);
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
int diag_id = i + j;
diags[diag_id].insert({i, j});
}
}
vvi ans(K, vi(K));
vvi diag_usage(n + 1);
int current_diag = 0;
for (int i = 0; i < (int)tour.size(); i++) {
int color = tour[i];
diag_usage[color].push_back(current_diag + 1);
while (current_diag < 3 * (i + 1)) {
for (auto [x, y] : diags[current_diag]) {
ans[x][y] = color;
}
++current_diag;
}
}
for (int u = 1; u <= n; u++) {
int idx = 0;
for (int diag_id : diag_usage[u]) {
for (auto [x, y] : diags[diag_id]) {
if (idx >= (int)adj[u].size()) break;
ans[x][y] = adj[u][idx++];
}
}
}
return ans;
}
