#include <iostream>
#include <fstream>
#include <queue>
#include <utility>

int n, m, start;
bool **mat;


void create_mat() {
    std::ifstream fin;
    int i, j;
    fin.open("bfs.in");
    fin >> n >> m >> start;
    mat = new bool* [n + 1];
    for (i = 1; i <= n; ++i) {
        mat[i] = new bool[n + 1];
        for (j = 1; j <=n; ++j)
            mat[i][j] = 0;
    }
    //
        int _m = m;
        while (_m--)
        {
            fin >> i >> j;
            mat[i][j] = 1;
        }
    fin.close();
}

void bfs() {
    std::queue<std::pair<int, int> > Q;
    bool viz[n + 1];
    int ans[n + 1];
    std::pair<int, int> crt;
    //
    for (int i = 1; i <= n; ++i) {
        ans[i] = -1;
        viz[i] = 0;
    }
    //
    Q.push( {start, 0} );
    viz[start] = 1;
    while (!Q.empty()) {
        crt = Q.front();
        Q.pop();
        ans[crt.first] = crt.second;
        //
        for (int i = 1; i <= n; ++i)
        {
            if (mat[crt.first][i] == 1 && viz[i] == 0)
            {
                Q.push( {i, crt.second + 1} );
                viz[i] = 1;
            }
        }
    }
    //
    std::ofstream fout;
    fout.open("bfs.out");
    for (int i = 1; i <= n; ++i)
        fout << ans[i] << ' ';
    fout.close();
    //
    for (int i = 1; i<=n; ++i)
    {
        for (int j = 1; j<=n; ++j)
        {
            std::cout << mat[i][j] << ' ';
        }
        std::cout << '\n';
    }
}


int main() {
    create_mat();
    bfs();
    return 0;
}