#include <stdio.h>
#include <vector>
#include <queue>
#define dim 100000

using namespace std;
vector <int> a[dim];
queue <int> q;
unsigned int n,m,s,c[dim];

void bfs()
{
    unsigned int i,nod;
    c[s]=1; //cost 1
    q.push(s); //add start node to queue
    while (!q.empty()) //queue not empty
    {
        nod = q.front();
        for (i=0;i<a[nod].size();i++)
            if (c[a[nod][i]]==0) //not visited
            {
                c[a[nod][i]]=c[nod]+1; //calculate cost
                q.push(a[nod][i]); //add in queue
            }
        q.pop();
    }
}

int main()
{
    unsigned int i,x1,x2;
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);
    s--;
    for (i=0;i<m;i++)
    {
        scanf("%d %d",&x1,&x2);
        a[x1-1].push_back(x2-1);
    }
    bfs();
    for (i=0;i<n;i++)
        printf("%d ",c[i]-1);
    return 0;
}