#include <fstream>
#include <list>
#include <queue>

using namespace std;

list <int> adiacList[100001];
int distNodes[100001];

int main()
{
    FILE * fin = fopen("bfs.in", "r");
    FILE * fout = fopen("bfs.out", "w");

    int m, n, x, i, j;
    fscanf(fin, "%d %d %d", &n, &m, &x);
    while(m--)
    {
        fscanf(fin, "%d %d", &i, &j);
        adiacList[i].push_back(j);
        /** Graful este orientat, adaugam doar intr-un sens **/
        //adiacList[j].push_back(i);
    }

    queue<int> q;
    q.push(x);
    distNodes[x] = 1;
    list<int>::iterator it, it_end;
    while (!q.empty())
    {
        j = q.front();
        i = distNodes[j] + 1;
        q.pop();
        for (it = adiacList[j].begin(), it_end = adiacList[j].end(); it != it_end; ++it)
        {
            if (!distNodes[*it])
            {
                distNodes[*it] = i;
                q.push(*it);
            }
        }
    }
    for (i = 1; i < n; ++i)
    {
        fprintf(fout, "%d ", distNodes[i] - 1);
    }
    fprintf(fout, "%d\n", distNodes[n]-1);

    fclose(fin);
    fclose(fout);
    return 0;
}