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

const int NMAX = 100000;
const int MMAX = 1000000;

vector <int> varf[1 + NMAX];
queue <int> index_varf;

int distanta[1 + NMAX];
bool vizitat[1 + NMAX];

int main()
{
    ifstream in("bfs.in");
    ofstream out("bfs.out");

    int n, m, s, a, b;
    int varf_crt;

    in >> n >> m >> s;
    distanta[s] = 0;
    vizitat[s] = 1;
    for(int i = 1; i <= m; i++)
    {
        in >> a >> b;
        varf[a].push_back(b);
    }

    index_varf.push(s);

    while(!index_varf.empty())
    {
        varf_crt = index_varf.front();
        index_varf.pop();
        for (size_t i = 0; i < varf[varf_crt].size(); i++)
        {
            if (!vizitat[varf[varf_crt][i]])
            {
                vizitat[varf[varf_crt][i]] = 1;
                index_varf.push(varf[varf_crt][i]);
                distanta[varf[varf_crt][i]] = distanta[varf_crt] + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if(distanta[i] == 0 && i != s)
        {
            out << -1;
        }
        else
        {
            out << distanta[i];
        }
        out << ' ';
    }

    return 0;
}