#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

vector<int> out[100001];

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int s, n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    scanf("%d", &s);
    --s;
    vector<int> distance(n, -1);
    distance[s] = 0;
    for(int i = 0; i < m; ++i)
    {
      int a, b;
      scanf("%d", &a);
      scanf("%d", &b);
        out[--a].push_back(--b);
    }
 
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int vertex1 = q.front();
        for(int i = 0; i < out[vertex1].size(); ++i)
        {
            int vertex2 = out[vertex1][i];
            if(distance[vertex2] == -1)
            {
                q.push(vertex2);
                distance[vertex2] = distance[vertex1] + 1;
            }
        }
        q.pop();
    }
 
    for(int i = 0; i < n; ++i)
      printf("%d ", distance[i]);
 
    return 0;
}