#include <bits/stdc++.h>
#define MAX 100001

using namespace std;

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

queue < int > Q;

int Mat[MAX][MAX];
bool Vizitat[MAX];
int D[MAX];
int N , M , X;

void BFS()
{
    int Nod , Next;
    while(!Q.empty())
    {
        Nod = Q.front();
        Q.pop();
        for(unsigned int i = 1 ; i <= N ; i++)
        {
            Next = Mat[Nod][i];
            if(D[Next] == -1)
            {
                Q.push(Next);
                D[Next] = D[Nod] + 1;
            }
        }
    }
}

int main()
{
    int i;
    fin >> N >> M >> X;
    for(i = 1 ; i <= M ; i++)
    {
        int A , B;
        fin >> A >> B;
        Mat[A][B] = B;
    }
    for(i = 1 ; i <= N ; i++)
    {
        D[i] = -1;
    }
    D[X] = 0;

    Q.push(X);
    BFS();

    for(i = 1 ; i <= N ; i++)
    {
        fout << D[i] <<" ";
    }
    return 0;
}