#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
int fix[245];
vector <vector <int> > build_mst(int N, const vector<vector<int> >& v)
{
vector <vector <int> > mst(N + 1);
vector <int> visited(N + 1, 0);
queue<int> q;
visited[1] = 1;
q.push(1);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int j = 0; j < v[u].size(); j++)
{
if(!visited[v[u][j]])
{
visited[v[u][j]] = 1;
mst[u].push_back(v[u][j]);
mst[v[u][j]].push_back(u);
q.push(v[u][j]);
}
}
}
return mst;
}
void DFS(int u, int parent, const vector<vector<int> >& mst, vector<int>& order)
{
order.push_back(u);
for(int j = 0; j < mst[u].size(); j++)
{
if(mst[u][j] != parent)
{
DFS(mst[u][j], u, mst, order);
order.push_back(u);
}
}
}
vector <vector <int> > create_map(int N, int M, vector<int> A, vector<int> B)
{
int i, j, k, ind;
vector < vector <int> > v(N + 1);
vector <int> order;
if(M == 0)
{
vector <vector<int> > mymap(1, std::vector<int>(1, 1));
return mymap;
}
for(i = 1; i <= N; i++)
{
v[i].clear();
}
order.clear();
for(i = 0; i < M; i++)
{
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
vector <vector <int> > mst = build_mst(N, v);
DFS(1, -1, mst, order);
vector <vector <int> > mymap(order.size() * 3, std::vector<int>(order.size() * 3, 0));
k = order.size() * 3;
ind = 0;
for(i = 0; i < k; i++)
{
if(i % 3 == 0)
{
for(j = 0; j < k; j++)
{
mymap[i][j] = order[ind];
}
ind++;
}
}
for(i = 0; i < k; i++)
{
if(i % 3 == 2)
{
for(j = 0; j < k; j++)
{
mymap[i][j] = mymap[i - 2][j];
}
}
}
for(i = 0; i < k; i++)
{
if(i % 3 == 1)
{
for(j = 0; j < v[mymap[i - 1][0]].size() * 2; j++)
{
if(j % 2 == 0) mymap[i][j] = mymap[i - 1][0];
else mymap[i][j] = v[mymap[i - 1][0]][j / 2];
}
}
}
for(i = 0; i < k; i++)
{
for(j = 0; j < k; j++)
{
if(mymap[i][j] == 0) mymap[i][j] = mymap[i - 1][j];
}
}
return mymap;
}
