#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <stack>
#include <bitset>
#include <list>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp(a,b) make_pair (a, b)
#define ll long long
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)

using namespace std;

int N, M, S;
vector <int> muchii[100010];
deque <pair <int, int> > QQ;
int visited[100010];

void Citire ()
{
    ifstream fin ("bfs.in");
    fin >> N >> M >> S;
    for (int i = 0, a, b; i < M; i++)
    {
        fin >> a >> b;
        muchii[a].pb (b);
    }
    fin.close ();
}

void Business ()
{
    QQ.pb (mp (S, 0));
    memset (visited, -1, sizeof (visited));
    visited[S] = 0;
    while (!QQ.empty ())
    {
        int a = QQ.back ().first;
        int b = QQ.back ().second;
        QQ.pob ();
        int nr = muchii[a].size ();
        for (int i = 0; i < nr; i++)
        {
            if (visited[muchii[a][i]] == -1)
            {
                visited[muchii[a][i]] = b + 1;
                QQ.pf (mp (muchii[a][i], b + 1));
            }
        }
    }
}

void Scriere ()
{
    ofstream fout ("bfs.out");
    for (int i = 1; i <= N; i++)
        fout << visited[i] << " ";
    fout.close ();
}

int main ()
{
    Citire ();
    Business ();
    Scriere ();
    return 0;
}