#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<vector<int>> mstAdj;
vector<bool> used;
vector<int> tour;
void DFS(int v)
{
used[v] = true;
tour.push_back(v);
for(int to : mstAdj[v])
{
if(!used[to])
{
DFS(to);
tour.push_back(v);
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
int i, j, v, ind, sz, k, val;
if(M == 0)
{
vector <vector<int>> mymap(1, std::vector<int>(1, 1));
return mymap;
}
adj.assign(N + 1, {});
mstAdj.assign(N + 1, {});
used.assign(N + 1, false);
for(i = 0; i < M; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(N + 1, false);
queue<int> q;
q.push(1);
visited[1] = true;
vector<pair<int, int>> mstEdges;
while(!q.empty())
{
v = q.front();
q.pop();
for(int to : adj[v])
{
if(!visited[to])
{
visited[to] = true;
q.push(to);
mstEdges.push_back({v, to});
mstAdj[v].push_back(to);
mstAdj[to].push_back(v);
}
}
}
DFS(1);
val = tour.size();
sz = val * 3;
vector <vector <int>> mymap(sz, std::vector<int>(sz, 0));
ind = 0;
for(i = 0; i < sz; i++)
{
if(i % 3 == 0)
{
for(j = 0; j < sz; j++)
{
mymap[i][j] = tour[ind];
}
ind++;
}
}
for(i = 0; i < sz; i++)
{
if(i % 3 == 2)
{
for(j = 0; j < sz; j++)
{
mymap[i][j] = mymap[i - 2][j];
}
}
}
//for(i = 0; i < tour.size(); i++)
//{
//cout << tour[i] << " ";
//}
for(i = 0; i < sz; i++)
{
if(i % 3 == 1)
{
k = 0;
for(j = 0; j < adj[mymap[i - 1][j]].size() * 2; j++)
{
if(j % 2 == 0) mymap[i][j] = mymap[i - 1][j];
else
{
mymap[i][j] = adj[mymap[i - 1][j]][k];
k++;
}
}
}
}
for(i = 0; i < sz; i++)
{
for(j = 0; j < sz; j++)
{
if(mymap[i][j] == 0) mymap[i][j] = mymap[i - 1][j];
}
}
return mymap;
}
