#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
vector<int> dfs_order;
vector<int> g[MAXN], allg[MAXN];
int par[MAXN];
int find(int x) {
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
par[y] = x;
}
void dfs(int node, int par) {
dfs_order.push_back(node);
for(int to: g[node]) {
if(to == par) continue;
dfs(to, node);
dfs_order.push_back(node);
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
if(N == 1) {
return {{1}};
}
for(int i = 0; i <= N; i++) {
par[i] = i;
g[i].clear();
allg[i].clear();
}
dfs_order.clear();
for(int i = 0; i < M; i++) {
allg[A[i]].push_back(B[i]);
if(find(A[i]) != find(B[i])) {
g[A[i]].push_back(B[i]);
unite(A[i], B[i]);
}
}
dfs(1, -1);
vector<vector<int> > the_map(4 * N, vector<int> (4 * N, 0));
int cur = 0;
for(int diagonal_sum = 0; diagonal_sum <= 8 * N; diagonal_sum++) {
cur = min(cur, (int)dfs_order.size() - 1);
if(diagonal_sum < 2 * N || diagonal_sum > 6 * N) {
for(int i = 0; i <= diagonal_sum; i++) {
int j = diagonal_sum - i;
if(i > 4 * N - 1 || j > 4 * N - 1) continue;
the_map[i][j] = dfs_order[cur];
}
continue;
}
if((diagonal_sum - 2 * N) % 3 != 1) {
for(int i = 0; i <= diagonal_sum; i++) {
int j = diagonal_sum - i;
if(i > 4 * N - 1 || j > 4 * N - 1) continue;
the_map[i][j] = dfs_order[cur];
}
}
else {
int curr = 0;
for(int i = 0; i <= diagonal_sum; i++) {
int j = diagonal_sum - i;
if(i > 4 * N - 1 || j > 4 * N - 1) continue;
the_map[i][j] = allg[dfs_order[cur]][curr];
curr = min(curr + 1, (int)allg[dfs_order[cur]].size() - 1);
}
}
if((diagonal_sum - 2 * N) % 3 == 2) {
cur += 1;
}
}
return the_map;
}
