#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>, int> edge_used;
vector<int> unused_graph[41], path_seq, expanded_seq;
int adj[41][41], seen[41], N_global, K_global;
static void build_path(int prev, int cur)
{
int nxt;
seen[cur] = 1;
for (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)
{
int i, j, col, v, u;
N_global = N;
if(M == 0)
{
vector<vector<int>> map_single(1, vector<int>(1, 1));
return map_single;
}
for(i = 1; i <= N_global; i++)
{
for(j = 1; j <= N_global; j++)
{
adj[i][j] = 0;
}
seen[i] = 0;
}
for(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(i = 1; i <= N_global; i++)
{
seen[i] = 0;
}
K_global = static_cast<int>(path_seq.size());
int unique_cnt = 0;
for(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 (col = 0; col < K_global; col++)
{
mymap[0][col] = expanded_seq[col];
}
for(u = 1; u <= N_global; u++)
{
for(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(i = 0; i < K_global; i++)
{
for(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;
}
