#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
const int NMAX=100001;
vector<int> graf[NMAX];
int d[NMAX];
queue<int> q;
int main()
{   int n,m,s,x,y;
    in>>n>>m>>s;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        //adaugam nodul y in lista de vecini ai nodului x
        graf[x].push_back(y);
    }
    /*for(int i=1; i<=n; i++)
    { out<<i<<":";
        for(int j=0; j<graf[i].size(); j++)
        {
            out<<graf[i][j]<<" ";
        }
        out<<endl;
    } */
    for(int i=1; i<=n; i++)
        d[i]=-1;
    //punem 0 la sursa
    d[s]=0;
    q.push(s);
    while(q.empty()==false)
    {
        x=q.front();
        q.pop();
        //parcurg vecinii nodului x
        for(int j=0; j<graf[x].size(); j++)
        {
            y=graf[x][j];
            if(d[y]==-1 || d[y]>d[x]+1)
            {
                d[y]=d[x]+1;
                q.push(y);
            }

        }
    }
    for(int i=1; i<=n; i++)
        out<<d[i]<<" ";
    return 0;
}