#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
template<class T>
class Nod
{
private:
	T Info;
	Nod* Prev;
	Nod* Next;

public:
	Nod ();
	Nod (const T& info);
	Nod (const Nod& other);

	T GetInfo () const;
	Nod* GetNext () const;
	Nod* GetPrev () const;

	void SetInfo (const T& info);
	void SetNext (Nod* next);
	void SetPrev (Nod* prev);
};
template<class T>
class ListIterator
{
private:
	Nod<T>* Current;

public:
	ListIterator ();
	ListIterator (const ListIterator& other);

	T GetInfo () const;

	ListIterator& operator++();
	ListIterator& operator--();

	ListIterator operator++(int dummyValue);
	ListIterator operator--(int dummyValue);

	bool operator==(Nod<T>* isNULL);
	bool operator!=(Nod<T>* isNULL);

	bool operator==(const ListIterator& other);
	bool operator!=(const ListIterator& other);

     friend void SetInfo (ListIterator<T>& iterator, Nod<T>* nod);
};
template<class T>
class List
{
private:
	Nod<T>* First;
	Nod<T>* Last;
	unsigned int Size;

public:
	List ();
	List (const List& other);
	~List ();
    int GetSize();
	void PushBack (const T& info);
	void PushFront (const T& info);

	void PopBack ();
	void PopFront ();

	ListIterator<T> Begin ();
	ListIterator<T> End ();
};
 template<class T>
 class Queue
 {
       List<T>* l;
       Nod<T> *First;
       Nod<T> *Last;
       unsigned int Size;
    public:
        Queue();
        Queue(const Queue& other);
        ~Queue();
        void Push(const T& info);
        Nod<T>* ReturnFirst();
        void Pop();
        int Length();
        void ToString();
        ListIterator<T> Begin ();
	    ListIterator<T> End ();
	    int isEmpty();
    };
    template<class T>
Nod<T>::Nod () :
	Info (0),
	Next (NULL),
	Prev (NULL)
{
}
template<class T>
Nod<T>::Nod (const T& info) :
	Info (info),
	Next (NULL),
	Prev (NULL)
{
}
template<class T>
Nod<T>::Nod (const Nod& other) :
	Info (other.Info),
	Prev (other.Prev),
	Next (other.Next)
{
}
template<class T>
T Nod<T>::GetInfo () const
{
	return Info;
}
template<class T>
Nod<T>* Nod<T>::GetPrev () const
{
	return Prev;
}
template<class T>
Nod<T>* Nod<T>::GetNext () const
{
	return Next;
}
template<class T>
void Nod<T>::SetInfo (const T& info)
{
	Info = info;
}
template<class T>
void Nod<T>::SetNext (Nod<T>* next)
{
	Next = next;
}
template<class T>
void Nod<T>::SetPrev (Nod<T>* prev)
{
	Prev = prev;
}
template<class T>
ListIterator<T>::ListIterator () :
	Current (NULL)
{
}
template<class T>
ListIterator<T>::ListIterator (const ListIterator& other) :
	Current (other.Current)
{
}
template<class T>
T ListIterator<T>::GetInfo () const
{
	return Current->GetInfo ();
}
template<class T>
ListIterator<T>& ListIterator<T>::operator++ ()
{
	Current = Current->GetNext ();
	return *this;
}
template<class T>
ListIterator<T>& ListIterator<T>::operator-- ()
{
	Current = Current->GetPrev ();
	return *this;
}
template<class T>
ListIterator<T> ListIterator<T>::operator++ (int dummyValue)
{
	ListIterator<T> temp (*this);
	++ (*this);
	return temp;
}
template<class T>
ListIterator<T> ListIterator<T>::operator-- (int dummyValue)
{
	ListIterator<T> temp (*this);
	-- (*this);
	return temp;
}
template<class T>
bool ListIterator<T>::operator== (Nod<T>* isNULL)
{
	return Current == isNULL;
}
template<class T>
bool ListIterator<T>::operator== (const ListIterator<T>& other)
{
	return Current == other.Current;
}
template<class T>
bool ListIterator<T>::operator!= (Nod<T>* isNULL)
{
	return ! ((*this) == isNULL);
}
template<class T>
bool ListIterator<T>::operator!= (const ListIterator<T>& other)
{
	return ! ((*this) == other);
}
template<class T>
void SetInfo (ListIterator<T>& iterator, Nod<T>* nod)
{
	iterator.Current = nod;
}
template<class T>
List<T>::List() :

	First (NULL),
	Last (NULL)
{
}
template<class T>
List<T>::List(const List& other) :
	Size (other.Size)
{
	Nod<T>* iterator=other.First;
	while(iterator!=NULL)
    {
		PushBack(iterator->GetInfo());
		iterator=iterator->GetNext();
	}
}
template<class T>
List<T>::~List()
{
	Nod<T>* iterator=First;
	while(iterator!=NULL)
    {
		Nod<T>* purged=iterator;
		iterator=iterator->GetNext();
		delete purged;
	}
	First=Last=NULL;
}
template<class T>
int List<T>::GetSize()
{
    return Size;
}
template<class T>
void List<T>::PushBack(const T& info)
{
	Nod<T>* nod=new Nod<T>(info);
	if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	Last->SetNext(nod);
	nod->SetPrev(Last);
	Last=nod;
}
template<class T>
void List<T>::PushFront (const T& info)
{
	Nod<T>* nod=new Nod<T>(info);
	if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	nod->SetNext(First);
	First->SetPrev(nod);
	First = nod;
}
template<class T>
void List<T>::PopBack()
{
	if(Last==NULL)
    {
		return;
	}
	Nod<T>* purged=Last;
	Nod<T>* prev=Last->GetPrev();
	delete purged;
	if(prev==NULL)
    {
		First=Last=NULL;
		return;
	}
	prev->SetNext(NULL);
	Last=prev;
}
template<class T>
void List<T>::PopFront()
{
	if(First==NULL)
    {
		return;
	}
	Nod<T>* purged=First;
	Nod<T>* next=First->GetNext();
	delete purged;
	if(next==NULL)
	{
		First=Last=NULL;
		return;
	}
	next->SetPrev(NULL);
	First=next;
}
template<class T>
ListIterator<T> List<T>::Begin()
{
	ListIterator<T> listIterator;
	SetInfo(listIterator,First);
	return listIterator;
}
template<class T>
ListIterator<T> List<T>::End()
{
	ListIterator<T> listIterator;
	SetInfo(listIterator,Last);
	return listIterator;
}
template<class T>
Queue<T>::Queue() :
    First(NULL),
    Last(NULL),
    Size(0)
{
    List<T>* l=new List<T>();
}
template<class T>
Queue<T>::Queue(const Queue<T>& other) :
     Size(other.Size)
{
    Nod<T>* iterator=other.First;
    while(iterator!=NULL)
    {
        Push(iterator->GetInfo());
        iterator=iterator->GetNext();
    }
}
template<class T>
Queue<T>::~Queue()
{
    Nod<T>* iterator=Last;
	while (iterator!=NULL)
    {
		Nod<T>* purged=iterator;
		iterator=iterator->GetNext();
		delete purged;
	}
	First=Last=NULL;
}
template<class T>
void Queue<T>::Push(const T& info)
{
    Nod<T>* nod=new Nod<T>(info);
    if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	nod->SetNext(Last);
	Last=nod;
}
template<class T>
Nod<T>* Queue<T>::ReturnFirst()
{
    return First;
}
template<class T>
void Queue<T>::Pop()
{
    if(Last==NULL)
    {
        return;
    }
    Nod<T>* purged=First;
    if(Last==First)
    {
        delete purged;
        First=Last=NULL;
        return;
    }
    Nod<T>* iterator=Last;
    while(iterator->GetNext()!=First)
        iterator=iterator->GetNext();
    delete purged;
    iterator->SetNext(NULL);
    if(Last->GetNext()==NULL)
    {
        First=Last;
        return;
    }
    First=iterator;

}
template<class T>
int Queue<T>::Length()
{
    Nod<T>* iterator=Last;
    Size=0;
    while(iterator!=NULL)
    {
        Size++;
        iterator=iterator->GetNext();
    }
    return Size;
}
template<class T>
void Queue<T>::ToString()
{
 Nod<T>* iterator=Last;
 while(iterator!=NULL)
 {
     cout<<iterator->GetInfo()<<endl;
     iterator=iterator->GetNext();
 }
 return;
}
template<class T>
ListIterator<T> Queue<T>::Begin()
{
	ListIterator<T> listIterator;
	SetInfo(listIterator,First);
	return listIterator;
}
template<class T>
ListIterator<T> Queue<T>::End()
{
	ListIterator<T> listIterator;
	SetInfo(listIterator,Last);
	return listIterator;
}
template<class T>
int Queue<T>::isEmpty()
{
    if(Last==NULL) return 1;
    return 0;
}
int main()
{
	int s,n,m,a[100][100],cost[100],x,y,viz[100],temp,k;
	fstream f("bfs.in",ios::in);
	f>>n>>m>>s;
	cout<<"Numarul de varfuri din graf este:"<<n<<endl;
	cout<<"Numarul de arce din graf este:"<<m<<endl;
	cout<<"Nodul de plecare este:"<<s<<endl;
	while(!f.eof())
    {
        f>>x>>y;
        a[x][y]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
    f.close();
    fstream g("bfs.out",ios::out);
    Queue<int>* queue=new Queue<int>();
    queue->Push(s);
    temp=s;
    viz[s]=1;
    k=1;
    while(!queue->isEmpty())
    {
        queue->Pop();
        for(int i=1;i<=n;i++)
            if(a[temp][i]==1 && viz[i]==0 && temp!=i)
              {
                 queue->Push(i);
                 if(temp!=s)
                     k++;
                 cost[i]=k;
                 viz[i]=1;
              }
    if(queue->End()!=NULL)
       temp=queue->ReturnFirst()->GetInfo();
    }
    cost[s]=0;
    for(int i=1;i<=n;i++)
    {
        if(s!=i && cost[i]==0) cost[i]=-1;
    }
    for(int i=1;i<=n;i++)
        g<<cost[i]<<' ';
    g.close();
    return 0;
}