#include <fstream>
#include <queue>
#include <vector>
#define NMAX 100001
using namespace std;


ifstream f("bfs.in");
ofstream g("bfs.out");

///varianta 50 p

//int a[1001][1001];
//int n,m,s;
//int viz[2002];
//queue <int> q;
//int nc; //nodul curent
//int main()
//{
//    f>>n>>m>>s;
//    for(int i=1;i<=m;i++)
//    {
//        int x,y;
//        f>>x>>y;
//        a[x][y]=1;
//    }
//    for(int i=1;i<=n;i++)
//        viz[i]=-1;
//    viz[s]=0;
//    q.push(s);
//    while(!q.empty())
//    {
//        nc=q.front();
//        q.pop();
//        for(int i=1;i<=n;i++)
//            if(a[nc][i]==1 and viz[i]==-1) //vecin nevizitat al nodului curent
//        {
//            q.push(i);
//            viz[i]=viz[nc]+1;
//        }
//    }
//    for(int i=1;i<=n;i++)
//        g<<viz[i]<<" ";
//    f.close();
//    g.close();
//    return 0;
//}

///varianta 100 p

int n,m,s;
int viz[NMAX];
int nc,v;
vector <int> vv[NMAX];
queue <int> q;

int main()
{
    f>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        vv[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        viz[i]=-1;
    q.push(s);
    viz[s]=0;
    while(!q.empty())
    {
        nc=q.front();
        q.pop();
        for(int i=0;i<vv[nc].size();i++)
        {
            v=vv[nc][i]; //vecinul luat din vector
            if(viz[v]==-1)
            {
                q.push(v);
                viz[i]=1+viz[nc];
            }
        }
    }
    for(int i=1;i<=n;i++)
        g<<viz[i]<<" ";
    return 0;
}