UVA 1056 Degrees of Separation (UVALive 3569, World Finals >> 2006 - San Antonio)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010


int mat[55][55];

void warshall(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mat[i][j]=min(mat[i][j], mat[i][k]+mat[k][j]);
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, m;
    string s, s2;
    char ch;
    while(cin>>n>>m && n)
    {
        map<string, int>mp;
        int cnt=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mat[i][j]=1e9;

        for(int i=0;i<m;i++)
        {
            cin>>s>>s2;
            if(mp.find(s)==mp.end()) mp[s]=cnt++;
            if(mp.find(s2)==mp.end()) mp[s2]=cnt++;
            mat[mp[s]][mp[s2]]=mat[mp[s2]][mp[s]]=1;
        }

        warshall(n);
        int mx=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                mx=max(mx, mat[i][j]);
        if(mx==1e9) cout<<"Network "<<kk++<<": DISCONNECTED\n\n";
        else    cout<<"Network "<<kk++<<": "<<mx<<"\n\n";

    }
return 0;
}