#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

bool vizitat[100001];
int n, m, s, distanta[100001];
vector<int> muchii_din[100001];
queue<int> coada;

void citire() {
    f>>n>>m>>s;
    int a, b;
    for(int i=0; i<m; i++) {
        f>>a>>b;
        muchii_din[a].push_back(b);
    }
}

void bfs(int start) {
    coada.push(start);
    vizitat[start] = 1;

    while (!coada.empty()) {

        int i = coada.front();
        cout<<i<<": ";
        coada.pop();

        for (int j : muchii_din[i]) {
            cout << " _" << j << "_ ";

            if (vizitat[j] == 0) {

                coada.push(j);
                vizitat[j] = 1;
                distanta[j] = distanta[i] +1;
                cout << "A";

            }
            cout << endl;
        }


    }


}

int main() {
    citire();
    f.close();
    for(int i=1; i<n; i++)
        distanta[i]=-1;

    distanta[s]=0;
    bfs(s);

    for(int i=1; i<=n; i++)
        g<<distanta[i]<<' ';

    g.close();

}