#include "worldmap.h"
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;
static map<pair<int,int>, int> edge_used;
static vector<int> unused_graph[41];
static vector<int> path_seq;
static vector<int> expanded_seq;
static int adj[41][41];
static int seen[41];
static int N_global;
static int K_global;
static void build_path(int prev, int cur) {
seen[cur] = 1;
for (int nxt = 1; nxt <= N_global; ++nxt) {
if (!seen[nxt] && adj[cur][nxt] == 1) {
path_seq.push_back(cur);
build_path(cur, nxt);
}
}
if (cur != 1) {
path_seq.push_back(cur);
}
}
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
N_global = N;
if (M == 0) {
vector<vector<int>> map_single(1, vector<int>(1, 1));
return map_single;
}
for (int i = 1; i <= N_global; ++i) {
for (int j = 1; j <= N_global; ++j) {
adj[i][j] = 0;
}
seen[i] = 0;
}
for (int i = 0; i < M; ++i) {
int x = A[i];
int y = B[i];
adj[x][y] = 1;
adj[y][x] = 1;
}
path_seq.clear();
build_path(0, 1);
expanded_seq.clear();
edge_used.clear();
for (int i = 1; i <= N_global; ++i) {
seen[i] = 0;
}
K_global = static_cast<int>(path_seq.size());
int unique_cnt = 0;
for (int i = 0; i < K_global; ++i) {
int v = path_seq[i];
expanded_seq.push_back(v);
if (seen[v] == 0) {
expanded_seq.push_back(-1);
expanded_seq.push_back(v);
seen[v] = 1;
++unique_cnt;
if (unique_cnt == N_global) break;
}
}
K_global = static_cast<int>(expanded_seq.size());
vector<vector<int>> mymap(K_global, vector<int>(K_global, -1));
for (int col = 0; col < K_global; ++col) {
mymap[0][col] = expanded_seq[col];
}
for (int u = 1; u <= N_global; ++u) {
for (int v = 1; v < u; ++v) {
if (adj[v][u]) {
pair<int,int> e = make_pair(v, u);
if (edge_used[e] == 0) {
int pos = -1;
for (int idx = 0; idx < K_global; ++idx) {
if (expanded_seq[idx] == v) {
pos = idx + 1;
break;
}
}
if (pos != -1) {
for (int row = 0; row < K_global; ++row) {
if (mymap[row][pos] == -1) {
mymap[row][pos] = u;
mymap[row][pos - 1] = v;
mymap[row + 1][pos] = v;
mymap[row + 1][pos - 1] = v;
break;
}
}
}
edge_used[e] = 1;
}
}
}
}
for (int i = 0; i < K_global; ++i) {
for (int j = 0; j < K_global; ++j) {
if (mymap[i][j] == -1) {
if (i == 0) {
mymap[i][j] = mymap[i][j - 1];
} else {
mymap[i][j] = mymap[i - 1][j];
}
}
}
}
return mymap;
}
