#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]);
allg[B[i]].push_back(A[i]);
if(find(A[i]) != find(B[i])) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
unite(A[i], B[i]);
}
}
dfs(1, -1);
// cerr << "dfs order" << endl;
// for(int x: dfs_order) {
// cerr << x << " ";
// }
// cerr << endl;
vector<vector<int> > the_map(3 * N, vector<int> (3 * N, 0));
int cur = 0;
int curr = 0;
int max_curr = 0;
for(int diagonal_sum = 0; diagonal_sum <= 6 * N; diagonal_sum++) {
cur = min(cur, (int)dfs_order.size() - 1);
if(diagonal_sum % 3 != 1) {
for(int i = 0; i <= diagonal_sum; i++) {
int j = diagonal_sum - i;
if(i > 3 * N - 1 || j > 3 * N - 1) continue;
the_map[i][j] = dfs_order[cur];
}
}
else {
for(int i = 0; i <= diagonal_sum; i++) {
int j = diagonal_sum - i;
if(i > 3 * N - 1 || j > 3 * N - 1) continue;
the_map[i][j] = allg[dfs_order[cur]][curr];
max_curr = max(max_curr, curr);
curr = min(curr + 1, (int)allg[dfs_order[cur]].size() - 1);
}
}
if(diagonal_sum % 3 == 2 && max_curr == (int)allg[dfs_order[cur]].size() - 1) {
cur += 1;
curr = 0;
max_curr = 0;
}
}
return the_map;
}
