#include "worldmap.h"
#include <vector>
#include <map>
using namespace std;
map <pair<int,int>,int> mp;
vector <int> gr[41];
vector <int> ans,s;
int way[41][41],fix[41];
int n,k;
void go(int u,int v){
int n=gr[v].size();
for (int i=0;i<n;i++){
int w=gr[v][i];
if (w!=u) {
ans.push_back(v);
go(v,w);
}
}//i
if (v!=1) ans.push_back(v);
}
void go5(int u,int v){
fix[v]=1;
for (int i=1;i<=n;i++)
if (fix[i]==0 && way[v][i]==1) {
ans.push_back(v);
go5(v,i);
}
if (v!=1) ans.push_back(v);
}
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
n=N;
if (M==0) {
vector <vector<int>> mymap(1, std::vector<int>(1, 1));
return mymap;
}
// ****************** 1,2 ********************
if (M==N-1) {
for (int i=1;i<=N;i++) gr[i].clear();
for (int i=0;i<M;i++){
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
ans.clear();
go(0,1);
k=ans.size();
vector<vector<int>> mymap(k, std::vector<int>(k, 1));
for (int i=0;i<k;i++)
for (int j=0;j<k;j++) mymap[i][j]=ans[j];
return mymap;
} else {
// **************** 5 ********************
for (int i=1;i<=N;i++) {
for (int j=1;j<=N;j++) way[i][j]=0;
fix[i]=0;
}
for (int i=0;i<M;i++){
way[A[i]][B[i]]=1;
way[B[i]][A[i]]=1;
}
ans.clear();
go5(0,1);
s.clear(); mp.clear();
for (int i=1;i<=n;i++) fix[i]=0;
k=ans.size();
int cnt=0;
for (int i=0;i<k;i++){
s.push_back(ans[i]);
if (fix[ans[i]]==0) {
s.push_back(-1);
s.push_back(ans[i]);
fix[ans[i]]=1;
cnt++;
if (cnt==N) break;
}
}
k=s.size();
vector<vector<int>> mymap(k, std::vector<int>(k, -1));
for (int i=0;i<k;i++) mymap[0][i]=s[i];
for (int u=1;u<=n;u++)
for (int v=1;v<u;v++)
if (way[u][v]) {
pair <int,int> tmp=make_pair(v,u);
if (mp[tmp]==0){ // add(v,u);
int nom;
for (int i=0;i<k;i++)
if (mymap[0][i]==v) {nom=i; break;}
for (int i=0;i<k;i++)
if (mymap[i][nom+1]==-1) {
mymap[i][nom+1]=u;
mymap[i+1][nom]=mymap[i+1][nom+1]=mymap[i][nom];
break;
}
mp[tmp]=1;
}
}//u,v
for (int i=0;i<k;i++)
for (int j=0;j<k;j++)
if (mymap[i][j]==-1) {
if (i==0) mymap[i][j]=mymap[i][j-1];
else mymap[i][j]=mymap[i-1][j];
}
return mymap;
}//5
}
