#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int st, vector<int>g[], bool vis[], vector<vector<int>> &ans, int &sm, int n){
cout << st << endl;
vis[st]=1;
vector<int>anc;
for(int i : g[st]){
if(vis[i]){
anc.push_back(i);
}
}
for(int i = 0;i<=sm;i++){
int j = sm-i;
if(i>=n||j>=n)
continue;
ans[i][j]=st;
}
sm++;
if(anc.size()){
int in = 0;
for(int i = 0;i<=sm;i++){
int j = sm-i;
if(i>=n||j>=n)
continue;
ans[i][j]=anc[min(in,(int)anc.size()-1)];
in++;
}
sm++;
for(int i = 0;i<=sm;i++){
int j = sm-i;
if(i>=n||j>=n)
continue;
ans[i][j]=st;
}
sm++;
}
for(int i : g[st]){
if(vis[i])
continue;
dfs(i,g,vis,ans,sm,n);
sm++;
for(int i = 0;i<=sm;i++){
int j = sm-i;
if(i>=n||j>=n)
continue;
ans[i][j]=st;
}
sm++;
}
}
vector<vector<int>> create_map(int n, int m, vector<int> A, vector<int> B) {
vector<int>g[n];
for(int i = 0;i<m;i++){
A[i]--;
B[i]--;
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
bool vis[n];
fill(vis,vis+n,0);
vector<vector<int>>ans(2*n-1,vector<int>(2*n-1));
int t = 0;
dfs(0,g,vis,ans,t,2*n-1);
return ans;
}
