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

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

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

	void SetInfo (int info);
	void SetNext (Nod* next);
	void SetPrev (Nod* prev);
};
class ListIterator
{
private:
	Nod* Current;

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

	int GetInfo () const;

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

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

	bool operator==(Nod* isNULL);
	bool operator!=(Nod* isNULL);

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

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

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

	void PopBack ();
	void PopFront ();

	ListIterator Begin ();
	ListIterator End ();
};
class Queue
{
       List* l;
       Nod *First;
       Nod *Last;
       unsigned int Size;
    public:
        Queue();
        Queue(const Queue& other);
        ~Queue();
        void Push(int info);
        Nod* ReturnFirst();
        void Pop();
        int Length();
        void ToString();
        ListIterator Begin ();
	    ListIterator End ();
	    int isEmpty();
    };
    Nod::Nod () :
	Info (0),
	Next (NULL),
	Prev (NULL)
{
}

Nod::Nod (int info) :
	Info (info),
	Next (NULL),
	Prev (NULL)
{
}

Nod::Nod (const Nod& other) :
	Info (other.Info),
	Prev (other.Prev),
	Next (other.Next)
{
}

int Nod::GetInfo () const
{
	return Info;
}

Nod* Nod::GetPrev () const
{
	return Prev;
}

Nod* Nod::GetNext () const
{
	return Next;
}

void Nod::SetInfo (int info)
{
	Info = info;
}

void Nod::SetNext (Nod* next)
{
	Next = next;
}

void Nod::SetPrev (Nod* prev)
{
	Prev = prev;
}
ListIterator::ListIterator () :
	Current (NULL)
{
}

ListIterator::ListIterator (const ListIterator& other) :
	Current (other.Current)
{
}

int ListIterator::GetInfo () const
{
	return Current->GetInfo ();
}

ListIterator& ListIterator::operator++ ()
{
	Current = Current->GetNext ();
	return *this;
}

ListIterator& ListIterator::operator-- ()
{
	Current = Current->GetPrev ();
	return *this;
}

ListIterator ListIterator::operator++ (int dummyValue)
{
	ListIterator temp (*this);
	++ (*this);
	return temp;
}

ListIterator ListIterator::operator-- (int dummyValue)
{
	ListIterator temp (*this);
	-- (*this);
	return temp;
}

bool ListIterator::operator== (Nod* isNULL)
{
	return Current == isNULL;
}

bool ListIterator::operator== (const ListIterator& other)
{
	return Current == other.Current;
}

bool ListIterator::operator!= (Nod* isNULL)
{
	return ! ((*this) == isNULL);
}

bool ListIterator::operator!= (const ListIterator& other)
{
	return ! ((*this) == other);
}

void SetInfo (ListIterator& iterator, Nod* nod)
{
	iterator.Current = nod;
}
List::List() :

	First (NULL),
	Last (NULL)
{
}

List::List(const List& other) :
	Size (other.Size)
{
	Nod* iterator=other.First;
	while(iterator!=NULL)
    {
		PushBack(iterator->GetInfo());
		iterator=iterator->GetNext();
	}
}

List::~List()
{
	Nod* iterator=First;
	while(iterator!=NULL)
    {
		Nod* purged=iterator;
		iterator=iterator->GetNext();
		delete purged;
	}
	First=Last=NULL;
}
int List::GetSize()
{
    return Size;
}
void List::PushBack(int info)
{
	Nod* nod=new Nod(info);
	if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	Last->SetNext(nod);
	nod->SetPrev(Last);
	Last=nod;
}

void List::PushFront (int info)
{
	Nod* nod=new Nod(info);
	if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	nod->SetNext(First);
	First->SetPrev(nod);
	First = nod;
}

void List::PopBack()
{
	if(Last==NULL)
    {
		return;
	}
	Nod* purged=Last;
	Nod* prev=Last->GetPrev();
	delete purged;
	if(prev==NULL)
    {
		First=Last=NULL;
		return;
	}
	prev->SetNext(NULL);
	Last=prev;
}

void List::PopFront()
{
	if(First==NULL)
    {
		return;
	}
	Nod* purged=First;
	Nod* next=First->GetNext();
	delete purged;
	if(next==NULL)
	{
		First=Last=NULL;
		return;
	}
	next->SetPrev(NULL);
	First=next;
}

ListIterator List::Begin()
{
	ListIterator listIterator;
	SetInfo(listIterator,First);
	return listIterator;
}

ListIterator List::End()
{
	ListIterator listIterator;
	SetInfo(listIterator,Last);
	return listIterator;
}
Queue::Queue() :
    First(NULL),
    Last(NULL),
    Size(0)
{
    List* l=new List;
}
Queue::Queue(const Queue& other) :
     Size(other.Size)
{
    Nod* iterator=other.First;
    while(iterator!=NULL)
    {
        Push(iterator->GetInfo());
        iterator=iterator->GetNext();
    }
}

Queue::~Queue()
{
    Nod* iterator=Last;
	while (iterator!=NULL)
    {
		Nod* purged=iterator;
		iterator=iterator->GetNext();
		delete purged;
	}
	First=Last=NULL;
}
void Queue::Push(int info)
{
    Nod* nod=new Nod(info);
    if(First==NULL)
    {
		First=Last=nod;
		return;
	}
	nod->SetNext(Last);
	Last=nod;
}
Nod* Queue::ReturnFirst()
{
    return First;
}
void Queue::Pop()
{
    if(Last==NULL)
    {
        return;
    }
    Nod* purged=First;
    if(Last==First)
    {
        delete purged;
        First=Last=NULL;
        return;
    }
    Nod* iterator=Last;
    while(iterator->GetNext()!=First)
        iterator=iterator->GetNext();
    delete purged;
    iterator->SetNext(NULL);
    if(Last->GetNext()==NULL)
    {
        First=Last;
        return;
    }
    First=iterator;

}
int Queue::Length()
{
    Nod* iterator=Last;
    Size=0;
    while(iterator!=NULL)
    {
        Size++;
        iterator=iterator->GetNext();
    }
    return Size;
}
void Queue::ToString()
{
 Nod* iterator=Last;
 while(iterator!=NULL)
 {
     cout<<iterator->GetInfo()<<endl;
     iterator=iterator->GetNext();
 }
 return;
}
ListIterator Queue::Begin()
{
	ListIterator listIterator;
	SetInfo(listIterator,First);
	return listIterator;
}
ListIterator Queue::End()
{
	ListIterator listIterator;
	SetInfo(listIterator,Last);
	return listIterator;
}
int Queue::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* queue=new Queue();
    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;
}