#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int N, M, S;
vector<int> l[100001];
int d[1000001], viz[1000001];

void citire(const char *filename, int &N, int &M, int &S, vector<int> l[1000001])    {
    ifstream f(filename);
    f>>N>>M>>S;
    S--;
    int x, y;
    for(int i=0;i<M;i++)    {
        f>>x>>y;
        l[x-1].push_back(y-1);
    }
    f.close();
}

void bfs(int S) {
    int x;
    queue<int> c;
    c.push(S);
    viz[S] = 1;
    d[S] = 0;
    while(c.size() > 0) {
        x = c.front();
        c.pop();
        for(int i=0;i<l[x].size();i++)  {
            int y = l[x][i];
            if(viz[y] == 0) {
                c.push(y);
                viz[y] = 1;
                d[y] = d[x] + 1;
            }
        }
    }
}



int main()
{
    citire("bfs.in", N, M, S, l);

    for(int i=0;i<N;i++)
        d[i] = -1;

    bfs(S);

    ofstream g("bfs.out");

    for(int i=0;i<N;i++)
        g<<d[i]<<' ';
    g.close();

    return 0;

}