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

using namespace std;

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

#define nmax 100001

vector <int> a[nmax];
queue <int> coada;
int d[1000001];
int n,m,i,s,nodcurent,vecin,k1,k2;

void bfs()
{
    while(coada.empty()==0)
    {
        nodcurent=coada.front();
        coada.pop();

        for(unsigned int i=0;i<=a[nodcurent].size();i++)
        {
            vecin=a[nodcurent][i];
            if(d[vecin]==-1)
            {
                d[vecin]=d[nodcurent]+1;
                coada.push(vecin);
            }
        }

    }

}

int main()
{
    f>>n>>m>>s;

    for(i=1;i<=m;i++)
    {
        f>>k1>>k2;
        a[k1].push_back(k2);
    }
    for(i=1;i<=n;i++)
        d[i]=-1;
    coada.push(s);
    d[s]=0;

    bfs();

    for(i=1;i<=n;i++)
        g<<d[i]<<" ";

    return 0;
}