#define nMax 100001
#include <fstream>
#include <list>
#include <queue>

using namespace std;

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

 int n,m,s;
 int nod[nMax];

 list<int> node[nMax];
 queue<int> q;

int main()
{

    x>>n>>m>>s;

    for(int i=1; i<=n; i++)
        nod[i]=-1;

    int a,b;

    for(int i=0; i<m; i++)
    {
        x>>a>>b;

        node[a].push_back(b);
    }

    nod[s]=0;
    q.push(s);

    while(!q.empty())
    {
        int temp=q.front();
        for(list<int>::const_iterator j=node[temp].begin(); j!=node[temp].end(); j++)
            if(nod[*j]==-1)
            {
                nod[*j]=nod[temp]+1;
                q.push(*j);
            }

        //y<<temp<<' ';

        q.pop();
    }

    for(int i=1; i<=n; i++)
        y<<nod[i]<<' ';
    y<<'\n';

    return 0;
}