/**
* __ __ __ __
* \ \ / / \ \ / (_) _____
* \ \ / /_ _\ \ / / _ ___|_ _|
* \ \/ /| | | |\ \/ / | |/ _ \ | |
* \ / | |_| | \ / | | __/ | |
* \/ \__,_| \/ |_|\____||_|
*
* Author: VuViet
* Created: 2025-08-05 15:58
**/
#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
const int N = 50;
typedef vector<int> vi;
vi adj[N], ch[N], need[N];
int grid[2 * N][2 * N];
vector<vi> rows;
bool vis[N], back[N], seen[N];
int depth[N], p[N], tin[N], tout[N];
int dfs_ord[2 * N], len_ord, timer = 0;
void Init(int n, int m, vi a, vi b)
{
for (int i = 0; i <= n; ++i)
{
adj[i].clear(); ch[i].clear(); need[i].clear();
vis[i] = back[i] = seen[i] = 0;
depth[i] = tin[i] = tout[i] = p[i] = 0;
}
len_ord = 0;
rows.clear();
for (int i = 0; i < m; ++i)
{
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
}
void DFS(int u, int par)
{
vis[u] = 1, p[u] = par, tin[u] = ++timer;
for (int v : adj[u])
{
if (vis[v]) continue;
ch[u].push_back(v);
depth[v] = depth[u] + 1;
DFS(v, u);
}
tout[u] = timer;
}
void Mark(int n)
{
int id = 1;
for (int i = 2; i <= n; ++i)
if (depth[i] > depth[id])
id = i;
while (id != 1)
{
back[id] = true;
id = p[id];
}
}
void EulerWalk(int u)
{
dfs_ord[len_ord++] = u;
for (int v : ch[u])
if (!back[v])
{
EulerWalk(v);
dfs_ord[len_ord++] = u;
}
for (int v : ch[u])
if (back[v])
{
EulerWalk(v);
dfs_ord[len_ord++] = u;
}
}
vector<vi> create_map(int n, int m, vi a, vi b)
{
Init(n, m, a, b);
DFS(1, -1);
Mark(n);
EulerWalk(1);
for (int i = 0; i < m; i++)
{
int u = a[i], v = b[i];
if (u == p[v] || v == p[u]) continue;
if (tin[v] <= tin[u] && tout[v] >= tout[u])
swap(u, v);
need[v].push_back(u);
}
for (int i = 0; i < len_ord; ++i)
{
int x = dfs_ord[i];
rows.push_back({x});
if (!seen[x] && !need[x].empty())
{
rows.push_back(need[x]);
rows.push_back({x});
seen[x] = true;
}
}
while ((int)rows.size() < 4 * n - 1)
rows.push_back(rows.back());
for (int i = 0; i < 4 * n - 1; i++)
{
int sz = min(i + 1, 4 * n - i - 1);
while ((int)rows[i].size() < sz)
rows[i].push_back(rows[i].back());
int p = 0;
for (int x = 0; x < 2 * n; x++)
{
int y = i - x;
if (y >= 0 && y < 2 * n)
grid[x][y] = rows[i][p++];
}
}
vector<vi> res(7 * n, vi(7 * n));
for (int i = 0; i < 2 * n; ++i)
for (int j = 0; j < 2 * n; ++j)
res[i][j] = grid[i][j];
return res;
}
