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

#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define INF (int)1e9

const int mxN = 50;

int n, m, visit;
unordered_map<string, int> mp;
pair<string, string> edges[mxN * mxN];
int adj[mxN][mxN];
bool vis[mxN];

void dfs(int u, int p) {
	++visit;
	vis[u] = 1;
	for(int i = 0; i < n; ++i)
		if(adj[u][i] != INF && !vis[i])
			dfs(i, u);
	return;
}

int main() {
	fastio;
	int c = 0;
	while(cin >> n >> m && (n || m)) {
		mp.clear();
		cout << "Network " << ++c << ": ";
		for(int i = 0; i < m; ++i) {
			cin >> edges[i].first >> edges[i].second;
			mp[edges[i].first];
			mp[edges[i].second];
		}
		int cnt = 0;
		for(auto& s : mp)
			s.second = cnt++;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				if(i == j)
					adj[i][j] = 0;
				else
					adj[i][j] = INF;
			}
		}
		for(int i = 0; i < m; ++i) {
			adj[mp[edges[i].first]][mp[edges[i].second]] = 1;
			adj[mp[edges[i].second]][mp[edges[i].first]] = 1;
		}
		memset(vis, 0, sizeof(vis));
		visit = 0;
		dfs(0, -1);
		if(visit != n) {
			cout << "DISCONNECTED\n";
			continue;
		}
		for(int k = 0; k < n; ++k)
			for(int i = 0; i < n; ++i)
				for(int j = 0; j < n; ++j)
					if(adj[i][j] > adj[i][k] + adj[k][j])
						adj[i][j] = adj[i][k] + adj[k][j];
		int mx = 0;
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
				if(adj[i][j] != INF)
					mx = max(mx, adj[i][j]);
		cout << mx << "\n";
	}
	
	return 0;
}