#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
vector<int>adj[50];
vector<int>rt;
bool vis[100];
void dfs(int a){
vis[a]=1;
rt.pb(a);
vector<pair<int,int>>vc;
for(auto b:adj[a]){
vc.pb({(int)adj[b].size(),b});
}
sort(vc.begin(),vc.end());
adj[a].clear();
for(auto p:vc){
adj[a].pb(p.ss);
}
for(auto b:adj[a]){
if(vis[b])continue;
dfs(b);
rt.pb(a);
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
for(int i=1;i<=N;i++){
adj[i].clear();
}
for(int i=0;i<M;i++){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
rt.clear();
pair<int,int>p={INT_MAX,0};
for(int i=1;i<=N;i++){
vis[i]=0;
p=min(p,{(int)adj[i].size(),i});
}
dfs(p.ff);
reverse(rt.begin(),rt.end());
int h=N*3;
vector< vector< int> > v(h, vector<int> (h));
for(int i=0;i<h;i++){
for(int j=0;j<h;j++)v[i][j]=p.ff;
}
for(int i=0;i<rt.size();i++){
int x=i*3;
for(int j=0;j<=min(x,h-1);j++){
int k=x-j;
if(k>h-1)continue;
v[j][k]=rt[i];
}
x=i*3+2;
for(int j=0;j<=min(x,h-1);j++){
int k=x-j;
if(k>h-1)continue;
v[j][k]=rt[i];
}
x=i*3+1;
for(int j=0;j<=min(x,h-1);j++){
int k=x-j;
if(k>h-1)continue;
v[j][k]=rt[i];
}
vector<pair<int,int>>del;
for(int j=0;j<=min(x,h-1);j++){
int k=x-j;
if(k>h-1)continue;
int a=rt[i];
if(j<adj[a].size()){
v[j][k]=adj[a][j];
del.pb({a,adj[a][j]});
}
}
for(auto p:del){
erase(adj[p.ff],p.ss);
erase(adj[p.ss],p.ff);
}
}
return v;
}
