#include <cstdio>
#include <queue>

using namespace std;

int n,m,a[10000][10000],s,cost[100000],viz[100000];

queue <int> q;

void Read()
{
    int aux1,aux2;
    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",&aux1,&aux2);
        a[aux1][aux2] = 1;
    }
}

void BFS()
{
    for(int i=1;i<=n;i++)
    {
        cost[i] = -1;
        viz[i] = 0;
    }

    cost[s] = 0;
    viz[s] = 1;
    q.push(s);

    while(!q.empty())
    {
        for(int i=1;i<=n;i++)
        {
            if(a[q.front()][i] == 1 && viz[i] == 0)
            {
                cost[i] = cost[q.front()] + 1;
                viz[i] = 1;
                q.push(i);
            }
        }
        q.pop();
    }
}

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