# https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1571
from itertools import product

def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        dk = dist[k]
        for i in range(v):
            di = dist[i]
            for j in range(v):
                if di[j] > di[k] + dk[j]:
                    di[j] = di[k] + dk[j]


def dijkstra(graph, source):
    q = set()
    dist = {}
    for v in product(range(len(graph)), repeat=2):
        dist[v] = 10e310
        q.add(v)
    dist[source] = 1

    while len(q) > 0:
        best = 10e310
        for elem in q:
            if dist[elem] <= best:
                u = elem
                best = dist[elem]
        q.remove(u)
        a, b = u
        if a == b == 1:
            break
        for v in q:
            x, y = v
            if x == a or x == b or y == a or y == b: continue

            alt = dist[(a, b)] + graph[b][x] + graph[x][y] + graph[y][a] - 1
            if alt < dist[v]:
                dist[v] = alt
    return dist


case = 0
while True:
    case += 1
    n, m = map(int, input().split())
    if n == m == 0:
        break

    graph = [[10e310] * n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0

    for _ in range(m):
        x, y = map(int, input().split())
        graph[x - 1][y - 1] = 1
    floyd_warshall(graph)
    if graph[0][1] == 10e310 or graph[1][0] == 10e310:
        print("Network {}\nImpossible\n".format(case))
        continue
    res = dijkstra(graph, (0, 0))
    print("Network {}\nMinimum number of nodes = {}\n".format(case, res[(1, 1)]))