print(
    "task: Graf10\nПоиск всех маршрутов между городами с сортировкой по длине и лексикографически"
)

import random


def create_file():
    n = random.randint(4, 6)
    with open("FileName1", "w") as f:
        f.write(str(n) + "\n")
        for i in range(n):
            row = [str(random.randint(0, 1)) for _ in range(n)]
            f.write(" ".join(row) + "\n")


def read_graph():
    try:
        with open("FileName1") as f:
            n = int(f.readline())
            m = [list(map(int, f.readline().split())) for _ in range(n)]
        return n, m
    except:
        return None, None


def dfs(m, v, target, visited, path, all_paths):
    if v == target:
        all_paths.append(path[:])
        return
    for u in range(len(m)):
        if m[v][u] == 1 and u not in visited:
            visited.add(u)
            path.append(u)
            dfs(m, u, target, visited, path, all_paths)
            path.pop()
            visited.remove(u)


def solve(n, m, k1, k2):
    paths = []
    dfs(m, k1, k2, {k1}, [k1], paths)
    paths.sort(key=lambda x: (len(x), x))
    return paths


def write(paths):
    with open("FileName2", "w") as f:
        if not paths:
            f.write("-1\n")
        else:
            f.write(str(len(paths)) + "\n")
            for p in paths:
                f.write(" ".join(str(x + 1) for x in p) + "\n")


while True:
    print("\n1 - создать файл FileName1")
    print("2 - выполнить задачу (результат в FileName2)")
    print("0 - выход")
    c = input(">> ")
    if c == "1":
        create_file()
        print("FileName1 создан")
    elif c == "2":
        n, m = read_graph()
        if n is None:
            print("ошибка чтения FileName1")
            continue
        try:
            k1 = int(input("K1: ")) - 1
            k2 = int(input("K2: ")) - 1
        except:
            print("ошибка ввода")
            continue
        paths = solve(n, m, k1, k2)
        write(paths)
        print("результат записан в FileName2")
    elif c == "0":
        break