#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 1e5 + 5;
const int oo = 2e9;

int n, m, start;
int dist[Nmax];
vector <int> L[Nmax];
queue <int> q;

int main()
{
    fin >> n >> m >> start;

    int x, y;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;

        L[x].push_back(y);
    }

    for(int i = 1; i <= n; i++)
        dist[i] = oo;

    dist[start] = 0;
    q.push(start);

    while(!q.empty())
    {
        x = q.front();
        q.pop();

        for(auto i : L[x])
            if(dist[i] > dist[x] + 1)
            {
                dist[i] = dist[x] + 1;
                q.push(i);
            }
    }

    for(int i = 1; i <= n; i++)
        fout << (dist[i] == oo ? -1 : dist[i]) << " ";

    fin.close();
    fout.close();
    return 0;
}