#include <fstream>
#include <iostream>

using namespace std;

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

struct el
{
        int info;
        el *next;
};

el *nods[100005], *p, *q;
el *head, *curent, *another;
int distanta[100005], n, m, s, nodX, nodY, pas;
bool viz[100005];

void Adauga_Vecin(int x, int y)
{
        q = new el;
        q -> info = y;
        q -> next = nods[x];
        nods[x] = q;
}

void Adauga_inCoada(int nod)
{
        another = new el;
        another -> info = nod;
        another -> next = NULL;
        curent -> next = another;
        curent = another;
}

void Pop(el **nod)
{
        el *aux;
        aux = *nod;
        *nod = (*nod) -> next;
        delete aux;
}

void BFS()
{
        while(head != NULL)
        {
                int nodcurent = head -> info;
                ++pas;
                for(p = nods[nodcurent]; p != NULL; p = p -> next)
                {
                        if(viz[p -> info] == false)
                        {
                                Adauga_inCoada(p -> info);
                                viz[p -> info] = true;
                                distanta[p -> info] = pas;
                        }
                }
                Pop(&head);
        }
}

int main()
{
        f >> n >> m >> s;
        for(int i = 1; i <= m; ++i)
        {
                f >> nodX >> nodY;
                Adauga_Vecin(nodX, nodY);
        }
        for(int i = 1; i <= n; ++i) distanta[i] = -1;
        distanta[s] = 0; viz[s] = true;
        head = new el;
        head -> info = s;
        head -> next = NULL;
        curent = head;
        BFS();
        for(int i = 1; i <= n; ++i) g << distanta[i] << " ";
        return 0;
}