---

"""
Задача 3 (Graf9).
Поиск всех маршрутов из города K1 в город K2 с ровно P пересадками.
Маршруты сортируются лексикографически и выводятся в текстовый файл.
Также генерируется файл graph_viz.dot для визуализации графа с подсветкой найденных путей.
"""

class RouteFinder:
    def __init__(self):
        self.n = 0
        self.matrix = []
        self.k1 = 0
        self.k2 = 0
        self.target_length = 0
        self.all_routes = []

    def _dfs(self, current_city, current_path, visited_cities):
        if len(current_path) == self.target_length:
            if current_city == self.k2:
                self.all_routes.append(list(current_path))
            return

        for neighbor in range(self.n):
            if self.matrix[current_city][neighbor] == 1 and neighbor not in visited_cities:
                visited_cities.add(neighbor)
                current_path.append(neighbor)
                
                self._dfs(neighbor, current_path, visited_cities)
                
                current_path.pop()
                visited_cities.remove(neighbor)

    def _generate_dot_file(self):
        successful_edges = set()
        for route in self.all_routes:
            for step in range(len(route) - 1):
                successful_edges.add((route[step], route[step + 1]))

        filename = "graph_viz.dot"
        with open(filename, 'w', encoding='utf-8') as f:
            f.write("digraph G {\n")
            f.write("    rankdir=LR;\n")
            
            for i in range(self.n):
                for j in range(self.n):
                    if self.matrix[i][j] == 1:
                        if (i, j) in successful_edges:
                            f.write(f'    {i + 1} -> {j + 1} [color="red", penwidth=2.0];\n')
                        else:
                            f.write(f'    {i + 1} -> {j + 1} [color="black", penwidth=1.0];\n')
            f.write("}\n")
        print(f"Файл визуализации {filename} успешно создан.")

    def start(self):
        file_in = input("Введите имя входного файла (например, graf9_in.txt): ")
        file_out = input("Введите имя выходного файла (например, graf9_out.txt): ")

        try:
            with open(file_in, 'r', encoding='utf-8') as f:
                lines = [line.strip() for line in f.readlines() if line.strip()]

            if not lines:
                raise ValueError("Файл пуст.")

            self.n = int(lines[0])
            if self.n > 15:
                raise ValueError("По условию задачи N <= 15.")

            self.matrix = []
            for i in range(1, self.n + 1):
                row = [int(x) for x in lines[i].split()]
                if len(row) != self.n:
                    raise ValueError(f"Размер матрицы не совпадает с N в строке {i}.")
                self.matrix.append(row)

            self.k1 = int(input(f"Введите номер города вылета K1 (от 1 до {self.n}): ")) - 1
            self.k2 = int(input(f"Введите номер города прилета K2 (от 1 до {self.n}): ")) - 1
            p_transfers = int(input("Введите количество пересадок P: "))

            if not (0 <= self.k1 < self.n) or not (0 <= self.k2 < self.n):
                raise ValueError("Номера городов вне допустимого диапазона.")

            self.target_length = p_transfers + 2
            self.all_routes = []

            visited = set([self.k1])
            self._dfs(self.k1, [self.k1], visited)
            
            self.all_routes.sort()

            self._generate_dot_file()

            with open(file_out, 'w', encoding='utf-8') as fout:
                if not self.all_routes:
                    fout.write("-1\n")
                    print(f"Маршрутов не найдено. В файл {file_out} записано -1.")
                else:
                    fout.write(f"{len(self.all_routes)}\n")
                    for route in self.all_routes:
                        formatted_route = [str(city + 1) for city in route]
                        fout.write(" ".join(formatted_route) + "\n")
                    print(f"Найдено маршрутов: {len(self.all_routes)}. Результат сохранен.")

        except FileNotFoundError:
            print("Ошибка: Входной файл не найден.")
        except Exception as e:
            print(f"Ошибка: {e}")

if __name__ == "__main__":
    app = RouteFinder()
    app.start()