#include <bits/stdc++.h>
using namespace std;
static inline long long edge_key(int u, int v) {
if (u > v) std::swap(u, v);
return (static_cast<long long>(u) << 32) | static_cast<unsigned int>(v);
}
std::vector<std::vector<int>> create_map(int N, int M,
std::vector<int> A,
std::vector<int> B) {
// adjacency list + neighbor sets
std::vector<std::unordered_set<int>> neighbors(N + 1);
std::vector<std::vector<int>> adj(N + 1);
neighbors.reserve(N + 1);
adj.reserve(N + 1);
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
neighbors[u].insert(v);
neighbors[v].insert(u);
adj[u].push_back(v);
adj[v].push_back(u);
}
// Build a spanning tree walk (Euler tour sequence) via DFS
std::vector<char> visited(N + 1, 0);
std::vector<int> seq;
seq.reserve(2 * N + 5);
std::function<void(int)> dfs = [&](int u) {
visited[u] = 1;
seq.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
seq.push_back(u);
}
}
};
int start = 1;
dfs(start);
// Append any missing vertices (if disconnected)
{
std::vector<char> in_seq(N + 1, 0);
for (int x : seq) in_seq[x] = 1;
for (int v = 1; v <= N; v++) {
if (!in_seq[v]) seq.push_back(v);
}
}
int K = (int)seq.size();
std::vector<int> row0 = seq;
// needed edges
std::unordered_set<long long> needed_edges;
needed_edges.reserve((size_t)M * 2 + 10);
for (int i = 0; i < M; i++) {
needed_edges.insert(edge_key(A[i], B[i]));
}
std::vector<int> vertices;
vertices.reserve(N);
for (int v = 1; v <= N; v++) vertices.push_back(v);
// RNG
std::mt19937 rng((uint32_t)std::chrono::high_resolution_clock::now().time_since_epoch().count());
int max_attempts = 300;
for (int attempt = 0; attempt < max_attempts; attempt++) {
std::vector<std::vector<int>> rows;
rows.reserve(K);
rows.push_back(row0);
bool ok = true;
for (int i = 1; i < K; i++) {
std::vector<int> row(K, 0);
bool row_ok = true;
for (int j = 0; j < K; j++) {
int above = rows[i - 1][j];
int left = (j > 0 ? row[j - 1] : -1);
const auto& neigh_above = neighbors[above];
const std::unordered_set<int>* neigh_left = (left != -1 ? &neighbors[left] : nullptr);
std::vector<int> cand;
cand.reserve(N);
for (int c : vertices) {
// vertical condition
if (above != c && neigh_above.find(c) == neigh_above.end()) continue;
// horizontal condition
if (left != -1) {
if (left != c && neigh_left->find(c) == neigh_left->end()) continue;
}
cand.push_back(c);
}
if (cand.empty()) {
row_ok = false;
break;
}
std::uniform_int_distribution<int> dist(0, (int)cand.size() - 1);
row[j] = cand[dist(rng)];
}
if (!row_ok) {
ok = false;
break;
}
rows.push_back(std::move(row));
}
if (!ok) continue;
// verify every colour appears at least once
std::vector<char> present(N + 1, 0);
int cnt_present = 0;
for (const auto& r : rows) {
for (int x : r) {
if (!present[x]) {
present[x] = 1;
cnt_present++;
}
}
}
if (cnt_present < N) continue;
// compute edges that appear in the grid
std::unordered_set<long long> edge_set;
edge_set.reserve((size_t)K * (size_t)K * 2 + 10);
for (int i = 0; i < K; i++) {
for (int j = 0; j + 1 < K; j++) {
int u = rows[i][j], v = rows[i][j + 1];
if (u != v) edge_set.insert(edge_key(u, v));
}
}
for (int i = 0; i + 1 < K; i++) {
for (int j = 0; j < K; j++) {
int u = rows[i][j], v = rows[i + 1][j];
if (u != v) edge_set.insert(edge_key(u, v));
}
}
// check subset
bool subset_ok = true;
for (auto key : needed_edges) {
if (edge_set.find(key) == edge_set.end()) {
subset_ok = false;
break;
}
}
if (subset_ok) return rows;
}
// Fallback deterministic construction
K = std::max(N, 2 * (int)std::sqrt(2.0 * M) + 1);
if (K % 2 == 1) K += 1;
K = std::min(K, 240);
int block_w = 2;
int blocks_per_row = K / block_w;
std::vector<std::vector<int>> grid(K, std::vector<int>(K, 1));
for (int idx = 0; idx < M; idx++) {
int r = idx / blocks_per_row;
int c = (idx % blocks_per_row) * block_w;
if (r >= K || c + 1 >= K) break; // safety
grid[r][c] = A[idx];
grid[r][c + 1] = B[idx];
}
return grid;
}
