#include <cstdio>
#include <queue>

using namespace std;

int n,m,s;
int adi[2][1000000];
int cost[100000],viz[100000];

queue <int> q;

void Read()
{
    freopen ("bfs.in","r",stdin);
    freopen ("bfs.out","w",stdout);
    scanf("%i%i%i",&n,&m,&s);
    for(int i=1;i<=m;i++)
        scanf("%i %i",&adi[0][i],&adi[1][i]);
}

void Parcurgere()
{
    for(int i=1;i<=n;i++)
    {
        cost[i]=-1;
        viz[i]=0;
    }
    q.push(s);
    cost[s]=0;
    viz[s]=1;
    for(int i=1;i<=n;i++)
    {
        for(int i=1;i<=m;i++)
        {
            if(adi[0][i]==q.front() && viz[adi[1][i]]==0)
            {
                viz[adi[1][i]]=1;
                cost[adi[1][i]]=cost[q.front()]+1;
                q.push(adi[1][i]);
            }
        }
        q.pop();
    }
}

int main()
{
    Read();
    Parcurgere();
    for(int i=1;i<=n;i++)
        printf("%i ",cost[i]);
    return 0;
}