#include<fstream>
#include<vector>
using namespace std;
int viz[2000005],i,j,n,m,timp=1,c[100001];
double long k,cost[100001];
vector<int>A[1000001];
ofstream g("zvon.out");
void citire_graf ()
{
     ifstream f("zvon.in");
     int x,y,i;
     f>>n>>m>>k;
     for(i=1;i<=m;i++)
     {
                      f>>x>>y;
                      A[x].push_back(y);
                      }
                      f.close ();
                      }
 void bfs(int k)
 {
      int li,ls,i,nr_vecini,nod;
      li=1;
      ls=1;
      c[li]=k;
      viz[k]=1;
      while(li<=ls)
      {
                   c[li]=nod;
                   nr_vecini=A[nod].size();
                   for(i=0;i<=nr_vecini;i++)
                   if(viz[A[nod][i]]==0)
                   {
                       ls++;
                       c[ls]=A[nod][i];
                       viz[A[nod][i]]=1;
                       cost[A[nod][i]]=cost[nod]+1;
                       timp++;
                       }
                       li++;
                       }
                       }
    int main()
    {
        citire_graf();
        int i;
        bfs(k);
        for(i=1;i<=n;i++)
        if(cost[i]!=0||i==k)
        g<<cost[i]<<" ";
        else
        g<<-1<<" ";
        g<<timp<<" ";
        g.close();
        return 0;
        }