// Arup Guha
// 2/17/2023
// Solution to COP 4516 Ind Contest 6 Problem: Degrees of Separation

using namespace std;

#include <iostream>
#include <unordered_map>
#include <string>

#define min(a,b) ((a)<(b))?(a):(b)
#define max(a,b) ((a)>(b))?(a):(b)

int main() {

    int n, e, loop = 1;
    cin >> n >> e;

    while (n != 0) {

        int id = 0;

        // Store graph here. 100 = no edge
        int g[50][50];
        for (int i=0; i<n*n; i++)
            g[i/n][i%n] = 100;
        for (int i=0; i<n; i++)
            g[i][i] = 0;

        unordered_map<string,int> mymap;

        // Process edges - add to graph.
        for (int i=0; i<e; i++) {

            string s1, s2;
            cin >> s1 >> s2;

            if (mymap.find(s1) == mymap.end()) mymap.insert({s1, id++});
            if (mymap.find(s2) == mymap.end()) mymap.insert({s2, id++});

            int u = mymap.find(s1)->second;
            int v = mymap.find(s2)->second;
            g[u][v] = 1;
            g[v][u] = 1;
        }

        // Run Floyd's.
        for (int k=0; k<n; k++)
            for (int i=0; i<n; i++)
                for (int j=0; j<n; j++)
                    g[i][j] = min(g[i][j], g[i][k]+g[k][j]);

        // Get max distance.
        int res = 0;
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                res = max(res, g[i][j]);

        // Ta da!
        cout << "Network " << loop << ": ";
        if (res < 100)
            cout << res << endl << endl;
        else
            cout << "DISCONNECTED" << endl << endl;

        // Get next case.
        cin >> n >> e;
        loop++;
    }

    return 0;
}