#include<stdio.h>
struct Nod {
    int x;
    Nod *next;
};

Nod * a[100001];
int q[100001];
int dist[100001];
int m, s, x, y, n;
char viz[100001];

int insert(Nod * &u, int val)
{
    Nod * v = new Nod;
    v -> x = val;
    v -> next = u;
    u = v;
}
int bfs(int s)
{
    int cap = 1;
    int coada = 1;
    viz[s] = 1;
    q[1] = s;
    while (cap <= coada)
      {
          for(Nod *it = a[q[cap]]; it; it = it -> next)
           if (!viz[it->x])
          {
           coada ++;
           q[coada] = it -> x;
           viz[it->x] = 1;
           dist[it->x] = dist[q[cap]] + 1;
          }
        cap ++;
      }
    return 0;

}
int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n, &m, &s);
    for(int i = 1; i <= m; i++)
    {
     scanf("%d %d",&x,&y);
     insert(a[x],y);
    }
    for(int i = 1; i <= n; i++)
     dist[i] = -1;
    dist[s] = 0;
    bfs(s);
    for(int i = 1; i <= n; i++)
     printf("%d ", dist[i]);
    printf("\n");
    return 0;
}