#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <set>
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
int K = 2 * M + 1;
std::map<int, std::multiset<int>> graph;
for (int i = 0; i < M; ++i) {
graph[A[i]].insert(B[i]);
graph[B[i]].insert(A[i]);
}
int start = 1;
for (int i = 1; i <= N; ++i) {
if (graph[i].size() % 2 == 1) {
start = i;
break;
}
}
std::vector<int> euler_path;
std::stack<int> s;
s.push(start);
while (!s.empty()) {
int u = s.top();
if (graph[u].empty()) {
euler_path.push_back(u);
s.pop();
} else {
int v = *graph[u].begin();
graph[u].erase(graph[u].find(v));
graph[v].erase(graph[v].find(u));
s.push(v);
}
}
std::vector<std::vector<int>> map(K, std::vector<int>(K, 0));
int x = 0, y = 0;
int dx = 0, dy = 1;
for (int i = 0; i + 1 < (int)euler_path.size(); ++i) {
int a = euler_path[i];
int b = euler_path[i + 1];
map[x][y] = a;
map[x + dx][y + dy] = b;
x += dx;
y += dy;
if (y + 1 >= K) {
x += 2;
y = 0;
}
}
// Lấp ô chưa dùng bằng quốc gia 1
for (int i = 0; i < K; ++i)
for (int j = 0; j < K; ++j)
if (map[i][j] == 0)
map[i][j] = 1;
return map;
}
