#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
int u = A[i] - 1, v = B[i] - 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vector<int>> paths;
vector<vector<int>> used(N, vector<int>(N, 0));
// mark edges
for (int i = 0; i < M; i++) {
int u = A[i] - 1, v = B[i] - 1;
used[u][v] = used[v][u] = 1;
}
// extract paths
while (true) {
int start = -1;
for (int i = 0; i < N; i++) {
for (int j : adj[i]) {
if (used[i][j]) {
start = i;
break;
}
}
if (start != -1) break;
}
if (start == -1) break;
vector<int> path;
int cur = start, prev = -1;
while (true) {
path.push_back(cur);
int nxt = -1;
for (int v : adj[cur]) {
if (v != prev && used[cur][v]) {
nxt = v;
break;
}
}
if (nxt == -1) break;
used[cur][nxt] = used[nxt][cur] = 0;
prev = cur;
cur = nxt;
}
paths.push_back(path);
}
int rows = N;
int cols = max(1, (int)paths.size());
int K = max(rows, cols);
vector<vector<int>> grid(K, vector<int>(K, 1));
// place each path in a column
for (int c = 0; c < (int)paths.size(); c++) {
for (int r = 0; r < (int)paths[c].size(); r++) {
grid[r][c] = paths[c][r] + 1;
}
}
// ensure every country appears
for (int i = 0; i < N; i++) {
grid[i][0] = i + 1;
}
return grid;
}
