//#include<stdio.h>
//int arr[105][105]={},c[105]={}, n, m,cnt=0;
//void f(int a)
//{
// if (arr[a][0]==0)
// {
// return;
// }
// for(int i=1;i<=n;i++)
// {
// if (arr[a][i]==1 && c[i]==0)
// {
// cnt++;
// c[i]=1;
// arr[a][0]--;
// f(i);
// }
// }
//}
//int main()
//{
// int i, a, b;
// scanf("%d %d", &n, &m);
// for(i=1;i<=m;i++)
// {
// scanf("%d %d", &a, &b);
// arr[a][b]=1;
// arr[b][a]=1;
// arr[a][0]++;
// arr[b][0]
// }
// c[1]=1;
// f(1);
// printf("%d", cnt);
// return 0;
//}
#include<stdio.h>
int ar[1005][1005]={},arr[1005][1005]={},c[10005]={}, n, m,q[10005]={}, top=-1, w=-1;
void push(int a)
{
top++;
q[top]=a;
}
void dfs(int a)
{
if (c[a]<1)
{
c[a]=1;
printf("%d ", a);
}
for(int i=1;i<=n;i++)
{
if (ar[a][i]==1)
{
ar[a][i]=0;
ar[i][a]=0;
dfs(i);
}
}
}
void bfs()
{
while(top>w)
{
for(int i=w+1;i<=top;i++)
{
int a=q[i];
if (c[a]<1)
{
c[a]=1;
printf("%d ", a);
}
for(int j=1;j<=n;j++)
{
if (arr[a][j]==1 && c[j]==0)
{
arr[a][j]=0;
arr[j][a]=0;
push(j);
}
}
w++;
}
}
}
int main()
{
int k,i,a,b;
scanf("%d %d %d", &n, &m, &k);
for(i=1;i<=m;i++)
{
scanf("%d %d", &a, &b);
arr[a][b]=1;
arr[b][a]=1;
ar[a][b]=1;
ar[b][a]=1;
}
dfs(k);
printf("\n");
for(i=1;i<=n;i++)
{
c[i]=0;
}
push(k);
bfs();
return 0;
}