#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int NMAX=100000,MMAX=200000,inf=2000000;
int N,M,S,L[MMAX],now,poz[NMAX];
class coada
{
public:
struct ncoada
{
    int val;
    ncoada* next;
}*primul,*ultimul;
    coada(int a)
    {
        primul=new ncoada;
        primul->val=a;
        ultimul=primul;
        primul->next=NULL;

    }
    void push(int a)
    {
        if(primul)
        {
            ncoada *p=new ncoada;
            ultimul->next=p;
            p->val=a;
            ultimul=p;
            ultimul->next=NULL;
        }
        else
        {
            primul=new ncoada;
            primul->val=a;
            ultimul=primul;
            primul->next=NULL;
        }

    }
    int pop(int a)
    {
        ncoada *p=primul;
        primul=primul->next;
        delete p;
        return a;
    }
    int empty()
    {
        if(primul)
            return 0;
        else return 1;
    }
};

struct graf{
    int vecin;
    graf* urm;
}*v[NMAX];
void add(int nod, int vecin)
{
    graf * p=new graf;
    p->urm=v[nod];
    p->vecin=vecin;
    v[nod]=p;
}
void citire()
{
    int x,y;
    fin>>N>>M>>S;
    while(M--)
    {
        fin>>x>>y;
        add(x,y);
    }
}
void parcurgere()
{
    coada coad(S);
    now=S;
    do
    {
        now=coad.primul->val;
        graf* p=v[coad.pop(now)];
        while(p)
        {
            if(poz[p->vecin]==0)
            {
                coad.push(p->vecin);
                L[p->vecin]=L[now]+1;
                poz[p->vecin]=1;
            }
            p=p->urm;
        }
    }while(!coad.empty());
}

int main()
{
    citire();
    for(int j=1;j<=N;++j)
        if(j!=S)
            L[j]=inf;
    parcurgere();
    for(int j=1;j<=N;++j)
        if(L[j] && j!=S)
            fout<<j<<" = "<<L[j]<<"\n";
    else if(L[j]==0 && j!=S)
        fout<<j<<" = "<<-1<<"\n";
    else fout<<"S= "<<0<<"\n";
    return 0;
}