# Arup Guha
# 4/3/2026
# Solution to COP 4516 Problem: Relatives

# Runs floyd's on this adjacency matrix - destroys original and overwrites
# it with the shortest distance values. Okay for this problem.
def floydwarshalls(adj):

    n = len(adj)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j])

# Makes an adjacency matrix with no connections for this problem.
def mkAdj(n):

    g = []
    for i in range(n):
        tmp = []
        for j in range(n):
            if j != i:
                tmp.append(n+1)
            else:
                tmp.append(0)
        g.append(tmp)
        
    return g
            
def main():

    # Process cases.
    size = [int(x) for x in input().split()]
    loop = 1
    while size[0] != 0:

        g = mkAdj(size[0])
        nameMap = {}
        idx = 0

        # Processing input is annoying in Python.
        processed = 0
        while processed < size[1]:

            # First I get the tokens.
            toks = input().split()
            processed += len(toks)//2

            # Go through each edge.
            for i in range(0,len(toks),2):

                # Update name map.
                p1 = toks[i]
                p2 = toks[i+1]
                if not (p1 in nameMap):
                    nameMap[p1] = idx
                    idx += 1

                # Same here.
                if not (p2 in nameMap):
                    nameMap[p2] = idx
                    idx += 1

                # Get edge indexes and add to graph.
                u = nameMap[p1]
                v = nameMap[p2]
                g[u][v] = 1
                g[v][u] = 1

        # Now we can run Floyd-Warshall's.
        floydwarshalls(g)

        res = 0
        for i in range(len(g)):
            res = max(res, max(g[i]))

        if res < len(g):
            print("Network "+str(loop)+": "+str(res))
        else:
            print("Network "+str(loop)+": DISCONNECTED")
        print()

        # Get next.
        size = [int(x) for x in input().split()]
        loop += 1

# Go!
main()