#include <fstream>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

#define MAX 100001

vector <int> a[MAX];
queue <int> c;
int n, m, start, viz[MAX];

void read(void);
void BFS(int start);
void display(void);

int main()
{
    read();
    BFS(start);
    display();
    return 0;
}

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

void BFS(int start) {
    int z, i;
    c.push(start);
    viz[start] = 1;
    while(!c.empty()) {
        z = c.front();
        c.pop();
        for(i = 0; i < a[z].size(); i++) {
            if(!viz[a[z][i]]) {
                viz[a[z][i]] = viz[z] + 1;
                c.push(a[z][i]);
            }
        }
    }
}

void display() {
    for(int i = 1; i <= n; i++)
        g<<viz[i] - 1<<' ';
    g<<'\n';
}