#include"stdio.h"
#include"string.h"
#include"queue"
#include"stack"
#include"iostream"
#include"string"
#include"map"
#include"stdlib.h"
#define inf 99999999
#define M 1000009
using namespace std;
struct st
{
int u,v,w,next;
}edge[M];
int t,head[M],use[M],s[M],cnt,Stack[M],top,num;
struct node
{
int u,id;
}p[M];
void init()
{
t=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
edge[t].u=u;
edge[t].v=v;
edge[t].next=head[u];
head[u]=t++;
}
/*void DFS(int u)
{
use[u]=1;
printf("%d ",u);
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
DFS(v);
}
}*/
void DFS(int u)
{
int i;
top=0;
memset(use,0,sizeof(use));
Stack[++top]=u;
use[u]=1;
while(top)
{
int u=Stack[top];
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
{
use[v]=1;
Stack[++top]=v;
break;
}
}
if(i==-1)
{
printf("%d ",Stack[top]);
top--;
}
}
}
void dfs(int u)
{
use[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v])
{
dfs(v);
}
}
printf("%d ",u);
}
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=-1)
{
init();
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
DFS(1);
printf("
");
memset(use,0,sizeof(use));
dfs(1);
printf("
");
}
}