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

using namespace std;

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

struct nod{
    int nr, lungime, vizitat;
    vector <int> legaturi;
};

vector<nod> noduri;
queue<int> coada;
int n;

int parcurge(int i)
{
    int k;
    noduri[i].vizitat = 1;
    for (k = 0; k < noduri[i].legaturi.size(); k++)
        if (noduri[noduri[i].legaturi[k] - 1].vizitat == 0)
            parcurge(noduri[i].legaturi[k] - 1);
}

int main()
{
    int m, s, i, a, b;

    f>>n>>m>>s;
    for (i = 0; i  < n; i++)
    {
        nod nou;
        nou.nr = i + 1;
        nou.lungime = -1;
        nou.vizitat = 0;

        if (i == s - 1)
        {
           nou.lungime = 0;
           nou.vizitat = 1;
        }



        noduri.push_back(nou);
    }

    for (i = 0; i < m; i++)
    {
        f>>a>>b;
        //noduri[b-1].ordin++;
        noduri[a-1].legaturi.push_back(b);
    }

    coada.push(s - 1);

    while (!coada.empty())
    {
        cout<<coada.front()<<endl;
        int nodCurent = coada.front();
        int lg = noduri[nodCurent].lungime;
        for (i = 0; i < noduri[nodCurent].legaturi.size(); i++)
        {
            int nodNou = noduri[nodCurent].legaturi[i] - 1;
            if (noduri[nodNou].vizitat == 0)
            {
                noduri[nodNou].vizitat = 1;
                noduri[nodNou].lungime = lg + 1;
                coada.push(nodNou);
            }
        }


        coada.pop();
    }

    for (i = 0; i < n; i++)
        g<<noduri[i].lungime<<" ";

    return 0;
}