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

#define BUF 1<<17
char P[BUF], *p;

int GET();
void Check();

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

int N, M, S;
int Cost[100002];
vector <int> V[100002];
queue <int> Q;

void Read();
void BFS();

int main()
{
    Read();
    BFS();
    for (int i = 1; i <= N; ++i)
    {
        if (Cost[i] == 0x3f3f3f3f) os << "-1 ";
        else os << Cost[i] << ' ';
    }
    is.close();
    os.close();
}

void Read()
{
    p = P;
    N = GET();
    M = GET();
    S = GET();
    memset(Cost, 0x3f3f3f3f, sizeof(Cost));
    Cost[S] = 0; Q.push(S);
    int a, b;
    for (int i = 0; i < M; ++i)
    {
        a = GET(); b = GET();
        V[a].push_back(b);
    }
};

void BFS()
{
    for ( ; !Q.empty(); Q.pop())
    {
        for (int j = 0; j < V[Q.front()].size(); ++j)
        {
            if (Cost[V[Q.front()][j]] > Cost[Q.front()]+1)
            {
                Cost[V[Q.front()][j]] = Cost[Q.front()]+1;
                Q.push(V[Q.front()][j]);
            }
        }
    }
};

int GET()
{
    while (*p < '0' || *p > '9') ++p, Check();
    int X = 0;
    while (*p >= '0' && *p <= '9') X = X*10+(*p-'0'), ++p, Check();
    return X;
};

void Check()
{
    if (*p == '\0') is.get(P, BUF, '\0'), p = P;
};