#include <fstream>
#include <queue>
#define NMAX 100001

using namespace std;

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

int best[NMAX], i, n, m, start, x, y;
queue <int> q;

struct node
{
    int value;
    node *next;
};
node *v[NMAX];

void add(node *&father, int data)
{
    node *NewNode = new node;
    NewNode -> value = data;
    NewNode -> next = father;
    father = NewNode;
}

void initialize()
{
    for (i=1; i<=n; ++i)
        best[i] = -1;
    best[start] = 0;
}

void BFS(int x)
{
    q.push(x);

    while (!q.empty())
    {
        node *Node;

        int a = q.front();
        q.pop();

        for (Node = v[a]; Node != NULL; Node = Node -> next)
        if (best[Node -> value] == -1)
        {
            best[Node -> value] = best[a] + 1;
            q.push(Node -> value);
        }
    }
}

int main()
{
    f>>n>>m>>start;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y;
        add(v[x],y);
    }

    initialize();
    BFS(start);

    for (i=1; i<=n; ++i) g<<best[i]<<" ";
    g<<'\n';
    return 0;
}