#include <cstdio>
#include <vector>
#include <queue>
#define dim 100010

using namespace std;
int cost[dim];  // costul de la s la i
vector <int> mylist[dim];
queue <int> myqueue;
int n,m,s,x,y;
bool vizitat[dim];


bool bfs(int start)
{
    vector<int>::iterator it;
    for(it=mylist[start].begin();it!=mylist[start].end();it++)
    {
        if(!vizitat[*it])
        {
            vizitat[*it]=1;
            myqueue.push(*it);
            cost[*it]=cost[start]+1;
        }
    }
    myqueue.pop();
    if(!myqueue.empty())
    {
        start=myqueue.front();
        bfs(start);
    }
    else
    {
        return 0;
    }
}
int main()
{
    FILE *inFile;
    FILE *outFile;
    inFile = fopen("bfs.in","r");
    outFile= fopen("bfs.out","w");
    fscanf(inFile,"%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        fscanf(inFile,"%d %d",&a,&b);
        mylist[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
    {
        cost[i]=-1;
    }
    cost[s]=0;
    myqueue.push(s);vizitat[s]=1;bfs(s);
    for(int i=1;i<=n;i++)
    {
        fprintf(outFile,"%d ",cost[i]);
    }   fprintf(outFile,"\n");
    fclose(inFile);fclose(outFile);
    return 0;
}