#include <fstream>
#include <vector>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
const int DIM = 100001;
vector<int> a[DIM];
int m, n, s, q[DIM], d[DIM], st, dr = -1;
void citire();
int main()
{
    int x, y;
    citire();

    for(int i = 0; i <= n; ++i)
        d[i] = -1;

    q[++dr] = s;
    d[s] = 0;
    while(st <= dr)
    {
        x = q[st++];
        for(int i = 0; i < a[x].size(); ++i)
        {
            y = a[x][i];
            if(d[y] == -1)
            {
                q[++dr] = y;
                d[y] = 1 + d[x];
            }
        }
    }

    for(int i = 1 ; i <=  n; ++i)
        cout << (i == s ? 0 : d[i]) << ' ';
    return 0;
}

void citire()
{
    int x, y;
    cin >> n >> m >> s;
    for(int i = 0; i < m; ++i)
    {
        cin >> x >> y;
        a[x].push_back(y);
    }
}