//
//  main.cpp
//  BFS-parcurgere_in_latime
//
//  Created by Tereza Oprea on 14/10/2018.
//  Copyright © 2018 Tereza Oprea. All rights reserved.
//

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

using namespace std;

ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

int n, m, s;

vector <int> v[100010];

queue <int> cd;

int viz[100010], dist[100010];


int main()
{
    int x, y, front;
    fin >> n >> m >> s;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
        dist[i] = -1;
    }
    cd.push(s);
    dist[s] = 0;
    while (!cd.empty())
    {
        front = cd.front();
        cd.pop();
        for (auto it:v[front])
        {
            if (!viz[it])
            {
                cd.push(it);
                if (dist[it] == -1)
                    dist[it] = dist[front] + 1;
                else
                    dist[it] = min (dist[it], dist[front] + 1);
                viz[it]++;

            }
        }
        
        
    }
    for (int i=1; i<=n; i++)
        fout << dist[i] << ' ';
    
}