---

3
1 1 0
1 0 1
0 1 0


"""
Задача 1 (Graf1).
Подсчет степеней вершин неориентированного графа по матрице смежности.
Петли учитываются дважды. Результат выводится в порядке возрастания номеров вершин.
"""

class GraphDegreeCalculator:
    def __init__(self):
        self.n = 0
        self.matrix = []
        self.degrees = []

    def calculate_degrees(self):
        self.degrees = []
        for i in range(self.n):
            degree = sum(self.matrix[i]) + self.matrix[i][i]
            self.degrees.append(degree)

    def start(self):
        filename = input("Введите имя файла с матрицей (например, graf1.txt): ")

        try:
            with open(filename, '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])
            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"Ошибка в строке {i}: ожидалось {self.n} элементов.")
                self.matrix.append(row)

            for i in range(self.n):
                for j in range(self.n):
                    if self.matrix[i][j] != self.matrix[j][i]:
                        raise ValueError("Матрица неориентированного графа должна быть симметричной.")

            self.calculate_degrees()

            for i, deg in enumerate(self.degrees):
                print(f"Вершина {i + 1}: Степень {deg}")

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


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


4
0 1 1 0
0 0 0 1
0 0 0 1
0 0 0 0

"""
Задача 2 (Graf4).
Обход ориентированного графа в ширину (BFS) от заданной вершины K.
Вывод достижимых вершин в порядке их обхода.
"""

class BFSGraphSolver:
    def __init__(self):
        self.n = 0
        self.matrix = []
        self.visited = []
        self.result_path = []

    def bfs(self, start_vertex):
        self.visited = [False] * self.n
        queue = [start_vertex]
        self.visited[start_vertex] = True
        self.result_path = []

        while queue:
            current = queue.pop(0)
            self.result_path.append(current)

            for neighbor in range(self.n):
                if self.matrix[current][neighbor] > 0 and not self.visited[neighbor]:
                    self.visited[neighbor] = True
                    queue.append(neighbor)

    def start(self):
        filename = input("Введите имя файла с матрицей (например, graf4.txt): ")

        try:
            with open(filename, '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])
            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"Размер строки {i} не совпадает с N.")
                self.matrix.append(row)

            k_input = int(input(f"Введите номер начальной вершины K (от 1 до {self.n}): "))
            if not (1 <= k_input <= self.n):
                raise ValueError("Номер вершины вне допустимого диапазона.")

            self.bfs(k_input - 1)

            formatted_result = [str(v + 1) for v in self.result_path]
            print(" ".join(formatted_result))

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


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

4
0 1 1 0
0 0 1 1
0 1 0 1
0 0 0 0


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

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 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("Введите номер города вылета K1: ")) - 1
            self.k2 = int(input("Введите номер города прилета K2: ")) - 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()

            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()