#include<iostream>
#include<fstream>
using namespace std;
int a[20][20],c[20],v[20],ns,n;
int prim;
int ultim;
void citire(int a[20][20],int &n)
{
ifstream f("graf.in");
int x,y;
f>>n;
while(f>>x>>y)
a[x][y]=a[y][x]=1;
f.close();
}
void afisare(int a[20][20],int n)
{
cout<<"Matricea de adiacenta este : "<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
int exista_nod_nevizitat(int v[20],int n)
{
for(int i=1;i<=n;i++)
if(v[i]==-1)
return i;
return 0;
}
int main()
{ citire(a,n);
afisare(a,n);
for(int i=1;i<=n;i++)
v[i]=-1;
cout<<"Dati nodul de start : "; cin>>ns;
v[ns]=0;
cout<<"Parcurgerea in latime este : ";
cout<<ns<<" ";
prim=ultim=1;
c[ultim]=ns;
while(exista_nod_nevizitat(v,n)!=0)
{
if(prim<=ultim)
{//adaug la coada toate nodurile adiacente si nevizitate
for(int i=1;i<=n;i++)
if(a[c[prim]][i]==1)
if(v[i]==-1)
{
ultim++;
c[ultim]=i;
cout<<i<<" ";
v[i]=v[c[prim]]+1;
}
prim++;
}
else
{
ns=exista_nod_nevizitat(v,n);
v[ns]=0;
prim=ultim=1;
c[prim]=ns;
cout<<ns<<" ";
}
}
for(int i=1;i<=n;i++)
cout<<"Distanta minima dintre nodul "<<i<<" si "<<ns<<" este "<<v[i]<<endl;
return 0;
}