#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n, m, s;
vector<int> costuri(100010, -1);
int vecini[100010];
vector<int> listaAdiacenta[100010];
queue<int> coadaParcurgere;
void bfs(int nod)
{
    int i, j;
    coadaParcurgere.push(nod);
    while(!coadaParcurgere.empty()){
        for(int j=0;j<vecini[coadaParcurgere.front()];j++)
        if(costuri[listaAdiacenta[coadaParcurgere.front()][j]] == -1)
        {
            costuri[listaAdiacenta[coadaParcurgere.front()][j]] = costuri[coadaParcurgere.front()] + 1;
            coadaParcurgere.push(listaAdiacenta[coadaParcurgere.front()][j]);
        }
        coadaParcurgere.pop();
    }
}

int main()
{
    in>>n>>m>>s;
    for(int i=0;i<m;i++)
    {
        int x, y;
        in>>x>>y;
        listaAdiacenta[x-1].push_back(y-1);
    }
    for(int i=0;i<n;i++)
    {
        vecini[i] = listaAdiacenta[i].size();
    }
    costuri[s-1] = 0;
    bfs(s-1);
    for(int i=0;i<n;i++)
    {
        out<<costuri[i]<<" ";
    }

}