#include<fstream>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
long i,n,m,s,p,q,x,y,nr,a[1000][1000],d[1000],v[1000],viz[1000];
int main()
{
    f>>n>>m>>s;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][0]++;
        a[x][a[x][0]]=y;
    }
    p=1;
    v[p]=s;
    d[s]=0;
    viz[s]=1;
    q=1;
    while (p<=q && p<=n)
    {
        for (i=1;i<=a[v[p]][0];i++)
            if (viz[a[v[p]][i]]==0)
            {
                q++;
                v[q]=a[v[p]][i];
                viz[a[v[p]][i]]=1;
                d[a[v[p]][i]]=d[v[p]]+1;
            }
        p++;
    }
    for (i=1;i<=q;i++)
        g<<v[i]<<" ";
    g<<'\n';
    for (i=1;i<=n;i++)
        if (viz[i]!=0)
            g<<d[i]<<" ";
            else
                g<<"-1 ";
    return 0;
}