#include <fstream>

using namespace std;

 ifstream x ("bfs.in");
 ofstream y ("bfs.out");

 struct node
 {
     int i;
     node *next;
 };

 struct struct1
 {
     int i;
     bool pass;
 };

 int n,m,start;
 node *temp;
 node *temp2;
 node *temp3;
 node *current;
 node *queue;
 node *head[100000];
 struct1 vertix[100000];

int main()
{
    int i,p,v;

    x>>n>>m>>start;

    int X,Y;

    for(i=1;i<=m;i++)
    {
        x>>X>>Y;

        if(head[X]==NULL)
        {
            head[X]=new node();
            head[X]->i=Y;
            head[X]->next=NULL;
        }
        else
        {
            temp=new node();
            current=new node();

            temp=head[X];

            while(temp->next)
               temp=temp->next;

            current->i=Y;
            current->next=NULL;
            temp->next=current;
        }
    }
/*
    for(i=1;i<=n;i++)
    {
        y<<i<<" --> ";

        temp=head[i];

        while(temp)
        {
            y<<temp->i<<' ';
            temp=temp->next;
        }

        y<<'\n';
    }
    y<<'\n';
*/
    vertix[start].i=0;
    vertix[start].pass=true;
    queue=new node();
    queue->i=start;
    queue->next=NULL;
    temp=queue;
    temp2=queue;
    temp3=queue;

    while(temp)
    {
        p=temp->i;

        current=head[p];
        while(current)
        {
            if(vertix[current->i].pass==false)
            {
                v=current->i;

                vertix[v].i=vertix[p].i+1;
                vertix[v].pass=true;

                temp2=new node();
                temp2->i=v;
                temp2->next=NULL;
                temp3->next=temp2;
                temp3=temp2;
            }

            current=current->next;
        }

        temp=temp->next;
    }

    for(i=1;i<=n;i++)
       if(vertix[i].pass==false)
          vertix[i].i=-1;

    for(i=1;i<=n;i++)
       y<<vertix[i].i<<' ';
    y<<'\n';

    return 0;
}