#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n,m,a[10000][10000],v[10010],x,parc[10010],u;
void citire()
{
    int x1,y;
    fin>>n>>m>>x;
    for(int a1=1;a1<=m;a1++)
    {
        fin>>x1>>y;
        a[x1][y]=1;
    }
}
void fct(int p)
{
    if(p<=u)
    {
        for(int a1=1;a1<=n;a1++)
        {
            if(a[parc[p]][a1]==1 and v[a1]==0 and a1!=x)
            {
                v[a1]=v[parc[p]]+1;
                u++;
                parc[u]=a1;
            }
        }
        p++;
        fct(p);
    }
}
int main()
{
    citire();
    u=1;
    parc[1]=x;
    fct(1);
    for(int a1=1;a1<=x-1;a1++)
    {
        if(v[a1]==0) fout<<"-1 ";
        else fout<<v[a1]<<" ";
    }
    fout<<v[x]<<" ";
    for(int a1=x+1;a1<=n;a1++)
    {
        if(v[a1]==0) fout<<"-1 ";
        else fout<<v[a1]<<" ";

    }
}