#include <bits/stdc++.h>

using namespace std;

char outBuffer[800000]; int q = -1;

__attribute__((always_inline)) void put_int(int x)
{
    int digits = x > 999999999 ? 11 :
                 x > 99999999  ? 10 :
                 x > 9999999   ? 9  :
                 x > 999999    ? 8  :
                 x > 99999     ? 7  :
                 x > 9999      ? 6  :
                 x > 999       ? 5  :
                 x > 99        ? 4  :
                 x > 9         ? 3  : 2;

    for(int i = digits; --i; x /= 10)
    {
        outBuffer[q + i] = x % 10 + 48;
    }

    outBuffer[q = q + digits] = 10;
}

int vertices, edges, u, v, start, level[100001];

vector<int> adj[100001];

void BFS(int start)
{
    queue<int> q;

    q.push(start);

    level[start] = 1;

    while(!q.empty())
    {
        int current = q.front(); q.pop();

        for(int child : adj[current])
        {
            if(level[child] == 0)
            {
                q.push(child);

                level[child] = level[current] + 1;
            }
        }
    }
}

int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

    scanf("%d %d %d", &vertices, &edges, &start);

    for(int i = 1; i <= edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);
    }

    BFS(start);

    for(int i = 1; i <= vertices; i++)
    {
        put_int(level[i] - 1);
    }

    fwrite(outBuffer, 1, q, stdout);

    return 0;
}