#include <bits/stdc++.h>
#define nmax 100001

using namespace std;

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

vector <int > matrice[nmax];
deque <int> q;
bool viz[nmax];
int dist[nmax];
int nc;

void dfs(int nod)
{
    viz[nod]=true;
    for(int i=0;i< matrice[nod].size();i++){
        if(viz[matrice[nod][i]]==0)
            dfs(matrice[nod][i]);
    }
}

/*void bfs(int nod)
{
    dist[nod]=nc++;
    viz[nod]=true;
    q.push_back(nod);
    for(int i=0;i<matrice[nod].size();i++)
    {
        if(viz[matrice[nod][i]]==0)
            bfs(matrice[nod][i]);
    }
}*/

int main()
{
    int n,m,s;
    int x,y;
    f>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        matrice[x].push_back(y);
    }

    /*for(int i=1;i<=n;i++)
        if(viz[i]==0){
            dfs(i);
            nc++;
        }
*/
    q.push_back(s);
    memset(dist, -1 , nmax);
    dist[s]=0;
    viz[s]=1;
    int nod,sz;
    while(q.empty()==false)
    {
        nod=q[0];
        sz=matrice[nod].size();
        for(int i=0;i<sz;i++){
            if(viz[matrice[nod][i]]==0)
            {
                q.push_back(matrice[nod][i]);
                dist[matrice[nod][i]]=dist[nod]+1;
                viz[matrice[nod][i]]=1;
            }
        }
        q.pop_front();
    }

    for(int i=1;i<=n;i++)
        g<<dist[i]<<" ";
   // g<<nc;
    return 0;
}