UVa 1056 - Degrees of Separation

// UVa 1056 - Degrees of Separation

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;

int main() {
	int t = 0;
	int n, m;
	while ((cin >> n >> m) && (n || m)) {
		int nn = 0;
		map<string, int> id;
		int cost[51][51];
		memset(cost, 127, sizeof(cost));
		int oo = cost[0][0];
		for (int j = 0; j < m; j++) {
			string sa, sb;
			cin >> sa >> sb;
			if (id[sa] == 0)
				id[sa] = ++nn;
			if (id[sb] == 0)
				id[sb] = ++nn;
			cost[id[sa]][id[sb]] = 1;
			cost[id[sb]][id[sa]] = 1;
		}
		int sol;
		bool broken = false;
		if (nn != n)
			broken = true;
		else {
			for (int i = 1; i <= n; i++)
				cost[i][i] = 0;
			for (int k = 1; k <= n; k++)
				for (int i = 1; i <= n; i++)
					if (cost[i][k] != oo)
						for (int j = 1; j <= n; j++)
							if (cost[k][j] != oo && cost[i][j] > cost[i][k] + cost[k][j])
								cost[i][j] = cost[i][k] + cost[k][j];
			sol = 0;
			for (int i = 1; i <= n; i++) {
				for (int j = i + 1; j <= n; j++)
					if (cost[i][j] > sol)
						sol = cost[i][j];
				if (sol == oo) {
					broken = true;
					break;
				}
			}
		}
		t++;
		if (broken)
			printf("Network %d: DISCONNECTED\n", t);
		else
			printf("Network %d: %d\n", t, sol);
		printf("\n");
	}
	return 0;
}