#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=45;
vector<int>E[N];
bool was[N],Edge[N][N];
vector<int>edges[N];
vector<vector<int>>DFS(int u,int p=0){
was[u]=true;
vector<vector<vector<int>>>comps;
for(auto i:E[u])if(i!=p){
if(was[i])edges[i].pb(u);
else comps.pb(DFS(i,u));
}
int n=1,m=0;
for(auto a:comps){
n+=a.size()+1;
m=max(m,(int)a[0].size());
}
m+=2;
vector<vector<int>>res(n,vector<int>(m,0));
for(int i=0;i<n;i++)for(int j=0;j<=1;j++)res[i][j]=u;
for(int j=0;j<m;j++)res[0][j]=u;
int ct=1;
for(auto a:comps){
for(int i=0;i<a.size();i++)for(int j=0;j<a[0].size();j++){
res[ct+i][2+j]=a[i][j];
}
ct+=a.size();
for(int j=0;j<m;j++)res[ct][j]=u;
ct++;
}
if(m>=3){
for(int i=0;i<n;i+=2)res[i][2]=u;
}
ct=2;
for(auto v:edges[u]){
res[ct][1]=v;ct+=2;
}
for(int i=0;i<n;i++)for(int j=1;j<m;j++)if(res[i][j]==0)res[i][j]=res[i][j-1];
return res;
}
vector<vector<int>> create_map(int n,int m,vector<int>A,vector<int>B){
for(int i=0;i<N;i++){
E[i].clear();
edges[i].clear();
was[i]=false;
for(int j=0;j<N;j++)Edge[i][j]=false;
}
for(int i=0;i<m;i++){
E[A[i]].pb(B[i]);
E[B[i]].pb(A[i]);
Edge[A[i]][B[i]]=Edge[B[i]][A[i]]=true;
}
vector<vector<int>>res=DFS(1);
if(res.size()>res[0].size()){
for(int i=0;i<res.size();i++){
while(res[i].size()<res.size())res[i].pb(res[i].back());
}
}
while(res.size()<res[0].size())res.pb(res.back());
return res;
}
