#include <fstream>
#include <algrithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 100001;

vector <int> a[N];
queue <int> c;
int n,m,s;
int v[N];

ifstream f("bfs.in");
ofstream g("bfs.out");

void citire()
{
    int i, x, y;
    f >> n >> m >> s;
    for (i = 0; i < m; i++)
    {
        f >> x >> y;
        a[x].push_back(y);
    }
}

/*
parcurg lista de adiacenta a lui x:
for (size_t i = 0; i < a[x].size(); i++)
{
    y = a[x][i];//vecinul (succesorul) curent

}
*/

int main()
{
    int i,j,nr,aux;
    bool ok;

    citire();



        for(j=1; j<=n; j++)
            v[j] = -1;

        c.push(s);
        v[s] = 0;
        while(!c.empty())
        {
            aux = c.front();
            c.pop();


            for(j=0; j<a[aux].size(); j++)
            {
                if(v[a[aux][j]] == -1)
                {
                    c.push(a[aux][j]);
                    v[a[aux][j]] = 1 + v[aux];
                }
            }
        }
        adauga(s);
        while (nh != 0)
        {
            x = h[1];
            sterge();
            for (y vecin cu x)
            {
                if (d[y] == -1)
                {
                    d[y] = d[x] + cost(x,y);
                    adauga(y);
                }
                else
                    if (d[x] + cost(x,y) < d[y])
                    {
                        d[y] = d[x] + cost(x,y);
                        urca(poz[y]);
                    }
            }
        }

        for(i=1; i<=n; i++)
            g<<v[i]<<' ';

    return 0;
}