#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
// Đơn giản chỉ dành cho N <= 15.
// Ý tưởng: với mỗi cặp liền kề (u,v), tạo hai dòng 1×2 để thể hiện biên giới u-v và v-u.
// Sau đó, đảm bảo mỗi màu j xuất hiện ít nhất một lần bằng các dòng đơn sắc.
vector<vector<int>> create_map(int N, int M, vi A, vi B) {
// Số dòng cần: 2*M dòng cho các cặp, + N dòng cho mỗi quốc gia xuất hiện.
int R = max(2 * M + N, 2);
int K = R;
// Tạo bản đồ K×K, khởi tạo toàn bộ là màu 1 (hoặc bất kỳ).
vector<vector<int>> C(K, vector<int>(K, 1));
// Thêm các biên giới cho mỗi cặp liền kề.
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
int r1 = 2 * i;
int r2 = 2 * i + 1;
// Dòng thể hiện u cạnh v
C[r1][0] = u;
C[r1][1] = v;
// Dòng thể hiện v cạnh u
C[r2][0] = v;
C[r2][1] = u;
}
// Đảm bảo mỗi màu j xuất hiện ít nhất 1 lần
int base = 2 * M;
for (int j = 1; j <= N; ++j) {
int r = base + (j - 1);
C[r][0] = j;
C[r][1] = j;
}
return C;
}
