// 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
//#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)
//#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;
//}