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

using namespace std;

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

int n, m, node;
vector<vector<int>> v;
int dist[100010];

void BFS(int start)
{
    queue<pair<int, int>> q;

    dist[start] = 0;
    q.emplace(start, dist[start]);

    while(!q.empty())
    {
        cout << q.front().first << ' ' << q.front().second << '\n';

        int sze = v[q.front().first].size();

        for(int i = 0; i < sze; i++)
        {
            if(dist[v[q.front().first][i]] == -1)
            {
                dist[v[q.front().first][i]] = q.front().second + 1;

                q.emplace(v[q.front().first][i], dist[v[q.front().first][i]]);
            }
        }

        q.pop();
    }
}

int main()
{
    in >> n >> m >> node;

    v.resize(n + 5);

    memset(dist, -1, sizeof dist);

    for(int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;

        v[x].push_back(y);
    }

    BFS(node);

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

    out << '\n';

    return 0;
}