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

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

void ini()
{
    int i;
    for (i=0;i<dim;i++)
        c[i]=-1;
}

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

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