#include <stdio.h>
int A[1001][1001],C[1001],D[1001];
void DFS(int a,int b){
    printf("%d ",a);
    C[a]=1;
    for(int i=1;i<=b;i++)
    {
        if(A[a][i]==1 && C[i]==0)
        {
            DFS(i,b);
        }
    }
}
int BFS(int a,int b,int c,int d){
    C[a]=1;
    do{
        for(int i=1;i<=b;i++)
        {
            if(A[a][i]==1 && C[i]==0)
            {
                D[d++]=i;
                C[i]=1;
            }
        }
        c++;
        a=D[c];
    }while(c<d);
    return c;
}
int main() {
    int x,y,z,m,n,o;
    scanf("%d %d %d",&x,&y,&z);
    for(int i=1;i<=y;i++)
    {
        scanf("%d %d",&m,&n);
        A[m][n]=1;
        A[n][m]=1;
    }
    for(int i=0;i<x;i++)
    {
        C[i]=0;
    }
    DFS(z,x);
    printf("\n");
    for(int i=1;i<=x;i++)
    {
        C[i]=0;
    }
    D[0]=z;
    o=BFS(z,x,0,1);
    for(int i=0;i<o;i++)
    {
        printf("%d ",D[i]);
    }
}