#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
// Chỉ dành cho N <= 15: dùng giải pháp đơn giản O(N+M), K = max(2*M + N, 2)
vector<vector<int>> create_map(int n, int m, vi A, vi B) {
// Tính kích thước bản đồ
int R = max(2 * m + n, 2);
int K = R;
// Khởi tạo toàn màu 1
vector<vector<int>> C(K, vector<int>(K, 1));
// Mỗi cặp liền kề (u,v) tạo hai ô cạnh nhau trên hàng riêng
for (int i = 0; i < m; ++i) {
int u = A[i], v = B[i];
int r1 = 2 * i;
// Ô cạnh nhau: (r1,0)-(r1,1)
C[r1][0] = u;
C[r1][1] = v;
// Đảo: (r1+1,0)-(r1+1,1)
C[r1+1][0] = v;
C[r1+1][1] = u;
}
// Đảm bảo mỗi màu j xuất hiện ít nhất một lần
int base = 2 * m;
for (int j = 1; j <= n; ++j) {
int r = base + (j - 1);
if (r >= K) break;
// Đặt hai ô liên tiếp màu j
C[r][0] = j;
C[r][1] = j;
}
return C;
}
