#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("bfs.in");

bool mat[101][101];
int n, m, a, b;
vector< vector<int> > listaAd;
queue<int> coada;
int prec[100];


int N,M,S;
int noduri,muchii,x,y;
vector< vector<int> > ListaAdiacenta(bool aux)
{


    vector< vector<int> > listaAd(noduri+1);

    for(int i=0;i<muchii;i++)
    {
        f>>x>>y;
        listaAd[x].push_back(y);
        if(aux==0)
            listaAd[y].push_back(x);
    }
    return listaAd;
}
void afisareListaAdiacenta(vector<vector<int>> &lista)
{
    for(size_t x=1; x< lista.size();x++)
    {
        cout<<x<<": ";
        for(auto y:lista[x])
            cout<<y<<" , ";
        cout<<endl;
    }
    cout<<endl;
}


void BFS(vector<vector<int>> &listaAd,int N,int start)
{
    vector< bool > vizitate(n+1,0);

    for(int i=1;i<=N;i++)
        prec[i]=-1;
//    vizitate.assign(n + 1, 0);
    vizitate[start] = 1;
    coada.push(start);

    while( !coada.empty() )
    {
        int front = coada.front();
        coada.pop();

        for(int i = 0; i < listaAd[front].size(); i++)
        {
            int vecin = listaAd[front][i];
            if( !vizitate[vecin] ) {
                vizitate[ vecin ] = 1;
                prec[vecin]=front;
                coada.push( vecin );
            }
        }
    }
    for(int i=1;i<=N;i++)
        cout<<i<<" = "<< prec[i]<<endl;
    cout << '\n';

}

int SmallestPath(int start,int final)
{   int nr=0;
    int nod=final;
    while(prec[nod]!=-1 )
    {
        nr++;
        nod=prec[nod];
    }
    if(nod!=start)nr=-1;
    return nr;
}


//void dfs(int start) {
//    cout << start << " ";
//    viz[start] = 1;
//
//    for(int i = 0; i < lists[start].size(); i++) {
//        int vecin = lists[start][i];
//        if( !viz[vecin] ) {
//            dfs(vecin);
//        }
//    }
//}


int main()
{
//    auto lista=ListaAdiacenta(1);
//    BFS(lista,1);

//      bfs(1);
    f>>noduri>>muchii;
    f>>S;
    bool aux;
    cout<<"Orientat=1/neorientat=0?"<<endl;
    cin>>aux;
    auto listaAdiacenta= ListaAdiacenta(aux);
    afisareListaAdiacenta(listaAdiacenta);

    //  viz.assign(n + 1, 0);
    //  dfs(1);
    //  cout << '\n';
    BFS( listaAdiacenta,noduri,S);
    for(int i=1;i<=noduri;i++)
        cout << SmallestPath(S, i) << endl;

    return 0;
}