#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <bitset>
#define add push_back

using namespace std;
int n, m, s;
int sol[100005];
vector<int> v[100005];
queue<int> q;

void Citire()
{
   int i, x, y;
   scanf("%d %d %d", &n, &m, &s);
   for (i=0; i<m; i++)
   {
      scanf("%d %d", &x, &y);
      if (x!=y)
         v[x].add(y);
   }
}

void Solve()
{
   int a;
   vector<int>::iterator i;
   q.push(s);
   sol[s]=0;
   while (!q.empty())
   {
      a=q.front();
      q.pop();
      for (i=v[a].begin(); i!=v[a].end(); ++i)
         if (sol[*i]==-1 || sol[a]+1<sol[*i])
         {
            sol[*i]=sol[a]+1;
            q.push(*i);
         }
   }
}

void Afisare()
{
   int i;
   for (i=1; i<=n; ++i)
      printf("%d ", sol[i]);
}

int main()
{
   freopen("bfs.in", "r", stdin);
   freopen("bfs.out", "w", stdout);
   memset(sol, -1, sizeof(sol));
   Citire();
   Solve();
   Afisare();
   return 0;
}