#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;
}
for(i = 1; i <= N; i++)
{
adj[i].clear();
}
tour.clear();
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);
sz = 4 * N;
vector <vector<int>> mymap(sz, vector<int>(sz, 0));
map<int,bool> firstOcc;
int curRow = 0;
for(int node : tour)
{
if(!firstOcc[node])
{
firstOcc[node] = true;
int r1 = curRow++;
int r2 = curRow++;
for(int j = 0; j < sz; j++) mymap[r2][j] = node;
int col = 0;
for(int nei : adj[node])
{
if(col >= sz) break;
mymap[r1][col++] = node;
if(col >= sz) break;
mymap[r1][col++] = nei;
}
}
}
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 < sz; i++)
{
if(i % 3 == 1)
{
for(j = 0; j < sz; j++)
{
int node = mymap[i - 1][j];
if(node == 0) continue;
mymap[i][j++] = node;
for(int nei : adj[node])
{
if(j >= sz) break;
mymap[i][j++] = nei;
}
j--;
}
}
}
for(i = 1; i < sz; i++)
for(j = 0; j < sz; j++)
if(mymap[i][j] == 0)
mymap[i][j] = mymap[i-1][j];
return mymap;
}
