#include<fstream>
#include<queue>
#include<iostream>
#include<vector>
#define maxn 10005

using namespace std;

class graph {
    int n;
    vector <int> v[maxn];
    int dist[maxn];
    
    public:
    graph(int n) {
        this -> n = n;
        for (int i = 1; i <= n; i++)
            dist[i] = -1;    
    }
    
    void add_edge(int x, int y) {
        v[x].push_back(y);    
    }
    
    void distances(int s) {
        int viz[n+5];
        for (int i = 1; i <= n; i++)
            viz[i] = 0;
        queue <int> c;
        c.push(s);
        dist[s] = 0;
        viz[s] = 1;
        while (!c.empty()) {
            int nod = c.front();
            c.pop();
            for (int i = 0; i < v[nod].size(); i++) {
                if (viz[v[nod][i]] == 0) {
                    dist[v[nod][i]] = dist[nod]+1;
                    viz[v[nod][i]] = 1; 
                    c.push(v[nod][i]);   
                } 
            }   
        }
    }
    
    void out(ofstream &g) {
        for (int i = 1; i <= n; i++)
            g << dist[i] << " ";
        g << '\n';
    }
};

int main() {
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    
    int n, m, s, x, y;
    f >> n >> m >> s;
    g << n << endl;
    
    graph gr = graph(n);
    for (int i = 1; i <= m; i++) {
        f >> x >> y;
        gr.add_edge(x, y);
    }
    gr.distances(s);
    gr.out(g);
    
    return 0;  
}