#include <iostream>
#include <list>
#include <fstream>

using namespace std;
ifstream f ("bfs.in");
ofstream g ("bfs.out");


class Graph
{
private:
    // Numar varfuri
    int v;
    // Lista de adiacenta
    list<int> *adj;
public:

    Graph(int V);

    void addEdge(int a, int b);

    void BFS(int s);
};

Graph::Graph(int V)
{
    v=V;
    adj = new list<int>[V+1];

}

void Graph::addEdge(int a, int b)
{
    adj[a].push_back(b);
}

void Graph::BFS(int s)
{
    //Vector vizitati initiat cu toate valorile fals
    int *visited=new int[v+1];
    for (int i=1; i<=v; i++)

        visited[i]=-1;

    //Creare coada pentru BFS
    list <int> q;
    visited[s]=0;
    q.push_back(s);
    while(!q.empty())
        {
            //Accesare prim element si eliminarea lui din coada
            s=q.front();
            q.pop_front();
            cout<<"Checking neighbours of: "<<s<<endl;

            //Adaugarea nodurilor nevizitate vecine in coada
            for(auto i = adj[s].begin(); i!=adj[s].end(); i++)
                {


                    if(visited[*i]==-1)
                    {


                     cout<<"Neighbour of distance "<<visited[s]+1<<": "<<*i<<endl;
                        visited[*i]=visited[s]+1;
                    q.push_back(*i);
                    }
                }
        }

        for(int i=1;i<=v;i++)
        {
            g<<visited[i]<<" ";
        }

}

int main()
{

    int n,m,s,x,y;
    f>>n>>m>>s;
    Graph g(n);
    cout<<"0"<<endl;
    for(int i=0;i<m;i++)
    {cout<<i<<" ";
        f>>x>>y;
        g.addEdge(x,y);
        cout<<i<<" ";

    }
    cout<<"1";


    g.BFS(s);


    return 0;
}