#include <iostream>
#include <fstream>
using namespace std;

int p[1000002], s[1000002], c[100000], cost[100000];
int n,m,g;

void bfs1()
{
    int i, j, k,cl;
    c[0]=g;
    j=1;
    cost[g]=0;
    for(cl=0; cl<m; cl++)
        if(s[cl]==g)
            p[cl]=-1;

    for(i=0; i<j; i++)
    {

        for(k=0; k<m; k++)
        {
            if(p[k]==c[i])
            {
                c[j]=s[k];
                cost[c[j]]=cost[c[i]]+1;
                for(cl=0; cl<m; cl++)
                    if(s[cl]==c[j])
                        p[cl]=-1;
                j++;
            }
        }
    }
}

int main()
{
    int i;
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    in>>n;
    in>>m;
    in>>g;
    cout<<m;
    for(i=0; i<m; i++)
        in>>p[i]>>s[i];
    in.close();
    for(i=0; i<n; i++)
    {
        cost[i]=-1;
    }
    bfs1();
    for(i=1; i<=n; i++)
{
        out<<cost[i]<<" ";

}
    return 0;
}