//100p var II cu liste de adiacenta(dinamic)
#include <fstream>
#include <vector>
#define NMAX 100003
using namespace std;
int n, m, u,p, s;
vector <int> A[NMAX];
int  C[NMAX];
int  viz[NMAX]; // (-1 pt. nod nevizitat)  (0 pt. nod de start)  (k lungimea drumului de la nodul)
ifstream fi("bfs.in");
ofstream fo("bfs.out");
void BF(int nod)
{
    int  j,nc;
    for(j=1;j<=NMAX-1;j++)viz[j]=-1;       // Marchez toate nodurile ca fiind nevizitate
    p=u=1;  viz[nod] = 0;  C[u] = nod;     //  Introduc nodul de start in coada
    while(p<=u)                              //  Elimin pe rand nodurile din coada
      {
         nc=C[p];                             //nc = nod curent
         for (j = 0; j < A[nc].size(); j++)   //  Parcurg vecinii nodului nc ce urmeaza sa fie eliminat
            if (viz[A[nc][j]] == -1)          // si se pun vecinii nevizitati a lui nc in coada
            {
                C[++u] = A[nc][j];            //  Adaug vecinii nevizitati in coada si le calculez distanta
                viz[C[u]] = viz[nc] + 1;
            }
       p++;
      }
}

int main()
{
   int i, x, y;

    fi>>n>>m>>s;
    //  Citesc arcele si retin graful sub forma de lista de vecini
    for(i=1;i<=m;i++)
    {
        fi>>x>>y;
        A[x].push_back(y);   //pune in lista nodului x nodul y
    }
    BF(s);
    for(i=1;i<=n;i++)
        fo<<viz[i]<<" ";
    fo<<'\n';
    return 0;
}
//// 50p cu mat. de adiacenta(nu incape)
//// Parcurgerea Breadth First(BF) var III  BFS infoarena
//#include <fstream>
//#define nmax 5600
//using namespace std;
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//int n,m,a[nmax][nmax],x,y,c[nmax],u,p,viz[nmax],i,v,s;
//void bfs(int x,int numar){
//    int i,p,u,v;
//    p=1; u=1;
//    c[1]=x; viz[x]=numar;
//    while(p<=u)
//    {
//      v=c[p];            //se ia nodul din varful cozii
//      for(i=1;i<=n;i++)
//        if(a[v][i]==1 && viz[i]==0)   //se cauta toti vecinii nevizitati
//        {                             //pentru nodul v
//          u++;
//          c[u]=i;                     //se pun in coada vecinii  gasiti
//          viz[i]=viz[v]+1;
//        }
//        p++;
//    }
//}
//int main()
//{
//    f >> n >> m >>s;
//    for(i=1;i<=m;i++)
//    {
//      f >> x >> y;
//      if(x!=y)a[x][y]=1;
//    }
//    bfs(s,1);
//
//     for(i=1;i<=n;i++) g<<viz[i]-1<<" ";
//     f.close(); g.close();
//    return 0;
//}
//
//// Parcurgerea Breadth First(BF) var II componentele conexe cu BF(nu are leg cu problema)
//#include <fstream>
//using namespace std;
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//int n,m,a[100][100],x,y,c[100],u,p,viz[100],i,v;
//void bfs(int x,int numar){
//    int i,p,u,v;
//    p=1; u=1;
//    c[1]=x; viz[x]=numar;
//    while(p<=u)
//    {
//      v=c[p];            //se ia nodul din varful cozii
//      for(i=1;i<=n;i++)
//        if(a[i][v]==1 && viz[i]==0)   //se cauta toti vecinii nevizitati
//        {                             //pentru nodul v
//          u++;
//          c[u]=i;                     //se pun in coada vecinii  gasiti
//          viz[i]=numar;
//        }
//        p++;
//    }
//    g <<"componenta "<< numar <<" -> ";
//    for(i=1;i<=u;i++)  g << c[i] << ' ';
//    g<<endl;
//}
//int main()
//{
//    f >> n >> m;
//    for(i=1;i<=m;i++)
//    {
//      f >> x >> y;
//      a[x][y]=1; a[y][x]=1;
//    }
//    int k=1;
//    for(i=1;i<=n;i++)
//     if(viz[i]==0){
//                   bfs(i,k);
//                   k++;
//     }
//     g<<endl;
//     for(i=1;i<=n;i++) g<<viz[i]<<" ";
//     f.close(); g.close();
//    return 0;
//}

//// Parcurgerea Breadth First(BF) clasica(nu are leg. cu problema)
//#include <fstream>
//using namespace std;
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//int n,m,a[100][100],x,y,c[100],u,p,viz[100],i,v;
//int main()
//{
//    f >> n >> m;
//    for(i=1;i<=m;i++)
//    {
//      f >> x >> y;
//      a[x][y]=1; a[y][x]=1;
//    }
//    f >> x;
//    p=1; u=1;
//    c[1]=x; viz[x]=1;
//    while(p<=u)
//    {
//      v=c[p];            //se ia nodul din varful cozii
//      for(i=1;i<=n;i++)
//        if(a[i][v]==1 && viz[i]==0)   //se cauta toti vecinii nevizitati
//        {                             //pentru nodul v
//          u++;
//          c[u]=i;                     //se pun in coada vecinii  gasiti
//          viz[i]=1;
//        }
//        p++;
//    }
//    g << "Parcurgerea BF" << '\n';
//    for(i=1;i<=u;i++)  g << c[i] << ' ';
//    f.close(); g.close();
//    return 0;
//}