#include <iostream>
#include <fstream>

using namespace std;
 ifstream f("date.in");
//SUBIECTUL 1.
int a[21][21],b[21][21],d[21],c[21],x[21],viz[21],n,m;
/*void citirehmat()
{
    int i,j,n;
            f>>n;
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)   // half of mat.
                f>>a[i][j];
                    a[j][i]=a[i][j];//formez intreaga matrice.
 f.close();
}
*/

/*void citirenm()
{int i,j;
f>>n>>m;
for(i=1;i<=n;i++)
    {f>>x>>y;
    a[x][y]=a[y][x]=1;}
    f.close();}
*/
void citiremat()
{
    int i,j,k;
        f>>n;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                f>>a[i][j];
                while(f>>k)
                {
                    m++;
                    x[m]=k;

                }
                f.close();
}
 void grade()
{int i,j;
    for(i=1;i<=n;i++)
        {int nr=0;
    for(j=1;j<=n;j++)
        if(a[i][j]==1)
            nr++;
        cout<<"Gradul vf "<<i<<" este: "<<nr<<endl;
        }}

void terminal()
{
    int i,j;
    bool ok=1;
    for(i=1;i<=n;i++)
    {   int nr=0;
        for(j=1;j<=n;j++)
        {if(a[i][j]==1)
            nr++;}
            if(nr==1)
            cout<<i<<" este varf terminal"<<endl;
            else ok=0;
        }
        if(ok==0) cout<<"Nu exista vf terminale"<<endl;
}
void izolat()
{
    int i,j;
    bool ok=1;
    for(i=1;i<=n;i++)
    {   int nr=0;
        for(j=1;j<=n;j++)
        {if(a[i][j]==1)
            nr++;}
            if(nr==0)
            cout<<i<<" este varf izolat"<<endl;
            else ok=0;

        }
        if(ok==0) cout<<"Nu exista vf izolate"<<endl;
}
void grmaxim()
{int i,j, max=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            d[i]=d[i]+a[i][j];
          for(i=1;i<=n;i++)
        if(d[i]>max)
        max=d[i];
    for(i=1;i<=n;i++)
       { if(d[i]==max)
        cout<<"varful "<<i<<" are gr.maxim = "<<max<<endl;
       }}

void afisare_muchii()
{   int i,j;
    for(i=1;i<=n;i++)
        {for(j=i+1;j<=n;j++)
         {if(a[i][j]==1)
            cout<<"( "<<i<<" "<<j<<" )";
         }
        cout<<endl;
        }
}
void liste()
{int i,j;
    for(i=1;i<=n;i++)
        {cout<<"vf "<<i<<" are vecini pe | ";
            for(j=1;j<=n;j++)
            {if(a[i][j]==1)
                cout<<j<<", ";
            }

        cout<<endl;
        }
}
void complet()
{
    int i,j,m=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(a[i][j]==1)m++;
                    m=m/2;
                if(m=n*(n-1)/2)
                        cout<<"Complet"<<endl;
                else cout<<"Nu este complet"<<endl;
}
int lant()
{
    int i,ok=1;
        for(i=1;i<m;i++)
                if(a[x[i]][x[i+1]]==0)
                    ok=0;
        return ok;
}
int elementar()
{
    int i,j,ok=1;
        if(lant()==1)
        {
            for(i=1;i<m;i++)
                for(j=1;j<=m;j++)
                if(x[i]==x[j])
                    ok=0;}
        else ok=0;
    return ok;
}
void Roy_Warshall()
{int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(b[i][j]==0&&i!=j&&i!=k&&j!=k)
                        b[i][j]=b[i][k]*b[k][j];
}
void conexitate_arbore()
{
    bool ok;
    int nr=0,j,i;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
         nr+=b[i][j];
    if(nr==n*(n-1)/2)
    {
        cout<<"Graful este conex"<<endl;
        if(m==n-1)  cout<<"Este arbore "<<endl;
            else cout<<"Nu este arbore "<<endl;
    }
    else cout<<"Graful nu este conex"<<endl;
}
void BF(int y)
{
    int x,pr,ult,j;
    pr=ult=1;
    c[ult]=y;
    viz[y]=1;
    while(pr<=n)
    {
        x=c[pr];
        if(a[x][j]==1&&viz[j]==0)
        {
            ult++;
            c[ult]=j;
            viz[j]=1;
        }
        pr++;
    }
}
void DF(int j)
{
    int i;
    viz[j]=1;
    cout<<j<<" ";
        for(i=1;i<=n;i++)
            if(a[j][i]==1&&viz[i]==0)
            DF(i);
}

int main()
{int i,k;
citiremat();
grade();
terminal();
izolat();
grmaxim();
afisare_muchii();
liste();
complet();
if(lant())
{
    cout<<"Este lant "<<endl;
    if(elementar())cout<<"Este elementar"<<endl;
        else cout<<"Nu este elementar"<<endl;
}
else cout<<"Nu este lant"<<endl;
Roy_Warshall();
conexitate_arbore();
cout<<"Dati nodul de pornire"<<endl;
    cin>>k;
    BF(k);
  for(i=1;i<=n;i++)
        if(c[i]!=0)
            cout<<c[i]<<" ";

    return 0;
}