#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

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

queue <int> c;

struct
{
    int viz, val;
}fr[300001];

int start[300001], t[2][2000001];

int main()
{
    int n, m, k, a, b, z = 0, nr, con = 1;
    f >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        f >> a >> b;
        z++;
        t[0][z] = b;
        t[1][z] = start[a];
        start[a] = z;
    }
    c.push(k);
    fr[k].viz = 1;
    while (c.empty() == 0)
    {
        nr = start[c.front()];
        con = fr[c.front()].val;
        while (nr != 0)
        {
            if (fr[t[0][nr]].viz == 0)
            {
                c.push(t[0][nr]);
                fr[t[0][nr]].val = con + 1;
                fr[t[0][nr]].viz = 1;
            }
            nr = t[1][nr];
        }
        c.pop();
    }
    for (int i = 1; i <= n; i++)
    {
        if (fr[i].val == 0 && i != k)
            g << -1 << " ";
        else
            g << fr[i].val << " ";
    }
    return 0;
}