#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
int sef[55];
int fre[55];
int find(int a)
{
if(sef[a]==a)
{
return a;
}
return sef[a]=find(sef[a]);
}
vector<int>adj[2005];
vector<int>veci[2005];
vector<int>euler;
vector<int>vec;
void dfs(int curr,int par)
{
euler.push_back(curr);
for(auto k:adj[curr])
{
if(k!=par)
{
dfs(k,curr);
euler.push_back(curr);
}
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
vector<vector<int>>mat;
int n=N,m=M;
euler.clear();
vec.clear();
for(int i=1; i<=n; i++)
{
sef[i]=i;
fre[i]=0;
adj[i].clear();
veci[i].clear();
}
for(int i=0; i<m; i++)
{
int a=find(A[i]);
int b=find(B[i]);
if(a!=b)
{
sef[b]=a;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
veci[A[i]].push_back(B[i]);
veci[B[i]].push_back(A[i]);
}
dfs(1,0);
int dim=3*n;
int diag=0;
for(auto x:euler)
{
diag++;
vec.push_back(x);
int cnt=0;
while(cnt<veci[x].size() && fre[x]==0)
{
diag++;
vec.push_back(-x);
cnt=cnt+min(diag,2*dim-diag);
diag++;
vec.push_back(x);
}
fre[x]=1;
}
while(vec.size()<2*dim-1)
{
vec.push_back(vec.back());
}
mat.resize(dim);
for(int i=0; i<dim; i++)
{
mat[i].resize(dim);
}
for(int p=0; p<dim*2-1; p++)
{
int i,j;
if(p<=dim-1)
{
i=p;
j=0;
}
else
{
i=dim-1;
j=p-dim+1;
}
if(vec[p]>0)
{
while(i>=0 && j<dim)
{
mat[i][j]=vec[p];
i--;
j++;
}
}
else
{
int curr=-vec[p];
while(i>=0 && j<dim)
{
if(veci[curr].size())
{
mat[i][j]=veci[curr].back();
veci[curr].pop_back();
}
else
mat[i][j]=curr;
i--;
j++;
}
}
}
return mat;
}
