#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
typedef struct node *node_ptr;
struct node
{
	int x;
	node_ptr next;
};
typedef node_ptr Queue;
typedef node_ptr LIST;
//============================
int
is_empty(Queue Q)
{
	return(Q->next==NULL);
}
//============================
Queue
create_queue(void)
{
	Queue Q;
	Q=(Queue) malloc(sizeof(struct node));
	if(Q==NULL)
		cout<<" out of space \n";
	Q->x=0;Q->next=NULL;
	return Q;
}
//=============================
void
make_null(Queue Q)
{
	if(Q != NULL)
		Q->next=NULL;
	else
		cout<<"  must use create queue first ";
}
//=============================
void
enqueue(int a,Queue Q)
{
	node_ptr extra,pos;
	pos=Q;
	extra=(node_ptr) malloc(sizeof(struct node));
	if(extra==NULL)
		cout<<"  out of space !!!\n" ;
	else
	{
		while(pos->next !=NULL)
			pos=pos->next;
		extra->x=a;extra->next=NULL;
		pos->next=extra;
	}
}
//=================================
int
dequeue(Queue Q)
{
	int r;
	node_ptr pos;
  /*	if(is_empty(q))
		{
		 cout<<" empty queue \n";
		 retu
	else
	{      */
		pos=Q->next;
		r=pos->x;
		Q->next=Q->next->next;
		free(pos);
	  return r;
}
//===================================
void
dispose_queue(Queue Q)
{
	LIST pos;
	pos=Q->next;
	Q->next=NULL;
	while(pos !=NULL)
	{
		free(pos);
		pos=pos->next;
	}
}
//===================================

//===================================

main()

{
 typedef struct node *node_prt;
 struct node
 {
	int x;
	node_ptr next;
 };
 typedef node_ptr List;
//===========================
typedef node_ptr Queue;
//===========================

 struct table_entry
 {
	List header;
	int known;
	int dist;
	int path;
 };
 typedef struct table_entry table[50];
 table t;


 //===========================
 int n,i,dat,v,w,j;
 int start;
 char ch;
 Queue Q;
 List extra;
 FILE  *p;
 //===========================
 /*
 p=fopen("c:\input.dat","w");
 fprintf(p,"%d ",7);
 fprintf(p,"%d ",3);
 fprintf(p,"%d ",1);fprintf(p,"%d ",2);
 fprintf(p,"%d ",1);fprintf(p,"%d ",4);
 fprintf(p,"%d ",3);fprintf(p,"%d ",1);
 fprintf(p,"%d ",3);fprintf(p,"%d ",6);
 fprintf(p,"%d ",4);fprintf(p,"%d ",3);
 fprintf(p,"%d ",4);fprintf(p,"%d ",5);
 fprintf(p,"%d ",4);fprintf(p,"%d ",6);
 fprintf(p,"%d ",4);fprintf(p,"%d ",7);
 fprintf(p,"%d ",2);fprintf(p,"%d ",4);
 fprintf(p,"%d ",2);fprintf(p,"%d ",5);
 fprintf(p,"%d ",5);fprintf(p,"%d ",7);
 fprintf(p,"%d ",7);fprintf(p,"%d ",6);
 fclose(p);   */
 do
 {

	/*
	for(i=n;i>0;i--)
	{
		t[i].known=0;
		t[i].dist=10000;
		t[i].path=0;
		extra=(List) malloc(sizeof(struct node));
		extra->x=0;
		extra->next=NULL;
		t[i].header=extra;
	}
	t[start].dist=0;   */
//===============




	 p=fopen("c:\input.dat","r");
	 fscanf(p,"%d",&dat);cout<<"\n";
	 n=dat;
	 fscanf(p,"%d",&dat);cout<<"\n";
	 start=dat;
// typedef struct table_entry table[50];
// table t;
//==============================
//cout<<" enter size\n";cin>>n;
//cout<<"enter start\n";cin>>start;
for(i=n;i>0;i--)
{
	t[i].known=0;
	t[i].dist=10000;
	t[i].path=0;
	extra=(List) malloc(sizeof(struct node));
	extra->x=0;
	extra->next=NULL;
	t[i].header=extra;
}
t[start].dist=0; 
//===============================
	do
	{
		fscanf(p,"%d",&v);
		fscanf(p,"%d",&w);
		cout<<"\n";
  //	for (i=1;i<=7;i++)
    //	{
   //	cout<<" input data \n";
 //	cin>>v>>w;
		extra=(List) malloc(sizeof(struct node));

		extra->x=w;
		extra->next=t[v].header->next;
		t[v].header->next=extra;
	}


	while(!feof(p));
	fclose(p);
//==================================
	Q=create_queue();make_null(Q);
	enqueue(start,Q);
	while(!is_empty(Q))
	{
		v=dequeue(Q);
		t[v].known=1;
		extra=t[v].header->next;



		while(extra !=NULL)
		{
			w=extra->x;
			if(t[w].dist==10000)
			{
				t[w].dist=t[v].dist+1;
				t[w].path=v;
				enqueue(w,Q);
			}
			extra=extra->next;
		}
	}
	dispose_queue(Q);
	clrscr();
        for (j=1;j<=5;j++) cout<<"\n";
	for(i=1;i<=n;i++)
	{
		for (j=1;j<=9;j++) cout<<" ";
		cout<<"	V["<<i<<"] : "<<"  DIST  = " <<t[i].dist;
		cout<<"  :   PATH = ";
		cout<<t[i].path<<"\n";
		cout<<"                --------------------------------\n";

	}
	for (j=1;j<=3;j++) cout<<"\n";
	cout<<"		continue    :    if  no  press  n  or  N \n  ";
	cout<<"                          else    press any other key\n";
	cin>>ch;
}
while ((ch !='n') && (ch !='N'));
return 0;
}