#include <vector>
#include <fstream>
#include <queue>
#include <iostream>

using namespace std;

#define maxn 100005

vector<int> muchii[maxn];

queue<int>coada;

int i,n,m,a,cost[maxn],vizitat[maxn],k,ok;

ifstream in("bfs.in");
ofstream out ("bfs.out");

void bfs(int nodinc)
{
    coada.push(nodinc);
    vizitat[nodinc]=1;
    cost[nodinc]=k;
    k++;
    while(!coada.empty())
    {
        nodinc=coada.front();
        coada.pop();
        for (vector<int>::iterator i=muchii[nodinc].begin();i!=muchii[nodinc].end();i++)
        if(vizitat[*i]!=1)
        {
            vizitat[*i]=1;
            cost[*i]=k;
            coada.push(*i);
            ok=1;
        }
        if (ok==1)
            k++;
        ok=0;
    }
}

int main ()
{

    int n1,n2;
    in>>n>>m>>a;
    for(i=1;i<=m;i++)
    {
        in>>n1>>n2;
        cout <<n1<<" "<<n2<<endl;
        muchii[n1].push_back(n2);
    }

    bfs (a);

    for(i=1;i<=n;i++)
        if(vizitat[i]!=1)
            cost[i]=-1;

    for(i=1;i<=n;i++)
        out <<cost[i]<<" ";
    return 0;
}