#include<iostream>
#include<fstream>
#include<stdio.h>
#include<bitset>
#include<queue>
#include<list>
using namespace std;
struct pl
{
    int d;
    int l;
};
list<int> l[100000];
bitset<100000> f;
void bfs(int n,int s)
{
    FILE* so=fopen("bfs.out","w");
    queue<pl> q;
    q.push({s,0});
    pl x;
    int d[n];
    d[s]=0;
    f[s]=1;
    list<int>::iterator i;
    while(q.size()>0)
    {
        x=q.front();
        q.pop();
        for(i=l[x.d].begin();i!=l[x.d].end();++i)
        {
            if(f[*i]==0)
            {
                d[*i]=x.l+1;
                q.push({*i,d[*i]});
                f[*i]=1;
            }
        }
    }
    int j;
    for(j=0;j<n;++j)
    {
        if(f[j]==1)
            fprintf(so,"%i ",d[j]);
        else
            fprintf(so,"-1 ");
    }
    fprintf(so,"\n");
}
int main()
{
    ifstream si;
    si.open("bfs.in");
    int n,m,s;
    si>>n>>m>>s;
    --s;
    int a,b,i;
    for(i=0;i<m;++i)
    {
        si>>a>>b;
        --a;
        --b;
        l[a].push_back(b);
    }
    bfs(n,s);
}