#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define st first
#define nd second
const int maxn = 109;
bool mat[maxn][maxn];
vector<vector<int>> ag;
int ng;
bool vis[maxn];
int aktr = 0;
int aktc = 0;
void DFS(int v)
{
vis[v] = 1;
for(int i = 0 ; i < 3*ng; i++)
{
ag[aktr][i] = v;
int p = i/2+1;
if(p > ng)continue;
if(i%2 == aktc)
{
if(mat[v][p])ag[aktr][i] = p;
}
}
aktr++;
aktc ^= 1;
for(int j = 1; j <= ng ; j++)
{
if(mat[v][j] && vis[j] == 0)
{
for(int i = 0; i < 3*ng ; i++)
{
if(i%2 == aktc)ag[aktr][i] = j;
else ag[aktr][i] = v;
}
aktr++;
DFS(j);
aktc ^= 1;
for(int i = 0; i < 3*ng ; i++)
{
if(i%2 == aktc)ag[aktr][i] = j;
else ag[aktr][i] = v;
}
aktr++;
aktc ^= 1;
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
ng = N;
if(M == 0)
{
return {{1}};
}
vector<vector<int>> ans(3*N,vector<int>(3*N,0));
ag = ans;
for(int i =0 ; i < M ; i++)
{
mat[A[i]][B[i]] = 1;
mat[B[i]][A[i]] = 1;
}
DFS(1);
while(aktr < 3*ng)
{
for(int i = 0 ; i< 3*ng;i++)ag[aktr][i] = 1;
aktr++;
}
for(int i = 1; i <= N ; i++)for(int j = 1; j <= N ; j++)mat[i][j] = 0;
for(int i = 1; i <= N ; i++)vis[i] = 0;
aktr = 0;
return ag;
}
