#include<iostream>
#include <conio.h>
#include <cstdlib>

using namespace std;

bool isconnected(const int* const *const ,int);
bool isconnect(const int *const*const,int,int,int,int*const);
int* fill(int*const,int,int);
bool exist(const int*const,int,int);
int findlen(const int*const*const,int,int,int,int*const);

int main()
{
    int n,**p;
    cout<<"enter count of vertex:";
    cin>>n;
    p=new int*[n];
    for(int i=0;i<n;++i)
      p[i]=new int[n];
    cout<<endl<<"enter matrix of connected graph."<<endl;
    for(int i=0;i<n;++i)
     for(int j=0;j<n;++j)
      cin>>p[i][j];
   if(!isconnected(p,n))
      cout<<"graph is not connected.";
   else
   {
       int d=0,*stack=new int[n];
       for(int i=0;i<n;++i)
         for(int j=0;j<n;++j)
           {
                 fill(stack,n,-1);
                 int m=findlen(p,n,i,j,stack);
                 cout<<i<<"-->"<<j<<" = "<<m<<endl;
                 d=d>m?d:m;
                 }
    cout<<endl<<endl<<"diameter ="<<d<<endl;
    delete []stack;
}
   for(int i=0;i<n;++i)
     delete []p[i];
    delete []p;
    getch();
   return 0;
}
bool isconnected(const int*const*const matrix,int row)
{
     int*stack=new int[row];
     for(int i= 0;i<row;++i)
       for(int j=i+1;j<row;++j)
       {
               if(!isconnect(matrix,row,i,j,fill(stack,row,-1)))
                  return false;
                  }
       return true;
}

bool isconnect(const int*const*const m,int row,int a,int b,int*const stack)
{
     if(m[a][b])
       return true;
     for(int i=0,j;i<row;i++)
     {
           if(m[a][i]&&!exist(stack,row,i))
           {
               for(j=0;stack[j]!=-1;++j);
               stack[j]=i;
               if(isconnect(m,row,i,b,stack))
                 return true;
                 }
         }
       return false;
}
int*fill(int*const a,int size,int value)
{
    for(int i=0;i<size;++i)
      a[i]=value;
    return a;
}
bool exist(const int*const list,int size,int n)
{
    for(int i=0 ; i < size && list[i]!=-1 ; ++i)
		if(list[i]==n)
			return true;
	return false;
}

int findlen(const int * const * const M ,int n ,int A ,int B,int *const stack)
{
	if(M[A][B])
		return 1;
	int len=n+1 , tmp;

	for(int i=0,j; i < n ; ++i)
	{
		if(M[A][B] && ! exist(stack,n,i))
		{
			for(j=0 ; stack[j]!=-1 ; ++j);
			stack[j]=i;

			if(tmp=findlen(M,n,i,B,stack))
				len=++tmp < len ? tmp : len;
			stack[j]=-1;
		}

	}
	return len==n+1? 0 : len;
}