#include <iostream>
#include <fstream>
#define len 10001

using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
bool matrix[len][len], viz[len];
int N, M, S, x, y, start, finish, que[len], v[len], l;
void bfs(int nod)
{
    start = finish = 1;
    que[start] = nod;
    viz[nod] = 1;
    while(start <= finish)
    {
        for(short i = 1; i <= N; ++i)
            if(matrix[que[start]][i] && !viz[i])
            {
                ++finish;
                que[finish] = i;
                viz[i] = 1;
                v[i] = l;
                ++l;
            }
        ++start;
    }
}
int main()
{
    in >> N >> M >> S;
    for(int i = 1; i <= M; ++i)
    {
        in >> x >> y;
        matrix[x][y] = 1;
    }
    bfs(S);
    for(int i = 1; i <= N; ++i)
        if(i == S)
            out << 0 << ' ';
        else if(!viz[i])
            out << -1 << ' ';
        else if(v[i])
            out << v[i] << ' ';
        else out << 1 << ' ';
    return 0;
}