#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
vector<vector<ll>> Graph,Tree;
map<ll,bool> vis;
void dfsTree(ll ind,ll par=-1){
if(par==-1)
{
vis.clear();
vis[ind]=true;
}
for(auto x:Graph[ind]){
if(vis[x])continue;
Tree[ind].push_back(x);
vis[x]=true;
dfsTree(x,ind);
}
}
map<ll,ll> keyInd;
vector<ll> line(ll ind,ll offset=0){
keyInd[ind]=offset;
vector<ll> ans(1,ind);
for(int i=0;i<Tree[ind].size();i++){
ans.push_back(ind);
ans.push_back(Tree[ind][i]);
vector<ll> temp=line(Tree[ind][i],offset+ans.size());
for(auto x:temp)ans.push_back(x);
ans.push_back(Tree[ind][i]);
}
return ans;
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
n=N,m=M;
Graph.clear();
Tree.clear();
Graph.resize(n);
Tree.resize(n);
for(int i=0;i<m;i++){
Graph[A[i]-1].push_back(B[i]-1);
Graph[B[i]-1].push_back(A[i]-1);
}
dfsTree(0);
vector<ll> ans=line(0);
vector<vector<int>> t(ans.size(),vector<int>(ans.size()));
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans.size();j++){
t[i][j]=ans[j]+1;
}
}
for(int i=0;i<n;i++){
cout<<keyInd[i]<<" ";
for(int j=0;j<Graph[i].size();j++){
t[2*j][keyInd[i]]=Graph[i][j]+1;
}
}
cout<<endl;
return t;
}
