#include <bits/stdc++.h>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct Item
{
    Item *next;
    int val;
};

struct Lista
{
    Item *st,*cur;
};

struct Mem
{
 int nod,dist;
};

int n,m,a,b,i,q;
Item *Elem;
Lista Adiac[100005];
bool Viz[100005];
int Distmin[100005];

void bfs(int);

int main()
{
    fin>>n>>m>>q;
    for (i=1;i<=n;i++)
     Distmin[i]=-1;
    Distmin[q]=0;
    for (i=1; i<=n; i++)
    {
        Adiac[i].st=new Item;
        Adiac[i].st->val=0;
        Adiac[i].st->next=0;
        Adiac[i].cur=Adiac[i].st;
    }
    while (m!=0)
    {
        m--;
        fin>>a>>b;
        Elem=new Item;
        Elem->val=b;
        Elem->next=0;
        Adiac[a].cur->next=Elem;
        Adiac[a].cur=Elem;
    }
    bfs(q);
    for (i=1;i<=n;i++)
     fout<<Distmin[i]<<" ";
    return 0;
}

void bfs(int nodst)
{
 Viz[nodst]=1;
 int st,sf,x;
 Item *i2;
 Mem Coada[100005];
 st=1;
 sf=1;
 Coada[1].nod=nodst;
 Coada[1].dist=0;
 while (st<=sf)
 {
  x=Coada[st].nod;
  if (Adiac[x].st->next!=NULL)
  {
   i2=Adiac[x].st->next;
   while (i2!=NULL)
   {
    if (Viz[i2->val]==0)
    {
     Viz[i2->val]=1;
     Distmin[i2->val]=Coada[st].dist+1;
     sf++;
     Coada[sf].nod=i2->val;
     Coada[sf].dist=Coada[st].dist+1;
    }
    i2=i2->next;
   }
  }
  st++;
 }
}