#include "worldmap.h"
#include <cassert>
#include <cstdio>
#include <vector>
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);
for(auto x:euler)
{
vec.push_back(x);
if(fre[x]==0)
{
fre[x]=1;
vec.push_back(-x);
vec.push_back(x);
}
}
int dim=vec.size();
mat.resize(dim);
for(int i=0;i<dim;i++)
{
mat[i].resize(dim);
if(vec[i]>0)
{
for(int j=0;j<dim;j++)
{
mat[i][j]=vec[i];
}
}
else
{
int curr=-vec[i];
for(int j=0;j<dim;j++)
{
if(j%2==1 && (j-1)/2<veci[curr].size())
{
mat[i][j]=veci[curr][(j-1)/2];
}
else
{
mat[i][j]=curr;
}
}
}
}
return mat;
}
