#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int n, m, s;
vector<int> l[100001];
int d[1000001], viz[1000001];

void citire(const char *fisier, int &n, int &m, int &s, vector<int> l[1000001])    {
    ifstream f(fisier);
    f>>n>>m>>s;
    s--;
    int x, y;
    for(int i=0;i<m;i++)    {
        f>>x>>y;
        l[x-1].push_back(y-1);
    }
    f.close();
}

void bfs(int s) {
    int x;
    queue<int> c;
    c.push(s);
    viz[s] = 1;
    d[s] = 0;
    while(c.size() > 0) {
        x = c.front();
        c.pop();
        for(int i=0;i<l[x].size();i++)  {
            int y = l[x][i];
            if(viz[y] == 0) {
                c.push(y);
                viz[y] = 1;
                d[y] = d[x] + 1;
            }
        }
    }
}



int main()
{
    citire("bfs.in", n, m, s, l);

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

    bfs(s);

    ofstream g("bfs.out");

    for(int i=0;i<n;i++)
        g<<d[i]<<' ';
    g.close();

    return 0;

}