D. Есть ли отрицательный цикл

Граф задан матрицей смежности; значение $10^5$ означает отсутствие ребра. Определите, есть ли в графе цикл отрицательного веса.

Приём стандартный: положить расстояния всех вершин равными нулю и выполнить $n$ фаз Форда — Беллмана. Нули вместо бесконечностей означают, что мы одновременно запускаем алгоритм из всех вершин сразу, — иначе цикл в другой компоненте остался бы незамеченным.

Если на $n$-й фазе хоть что-то улучшилось, отрицательный цикл есть. Обоснование: без отрицательного цикла любое расстояние достигается путём не более чем из $n - 1$ рёбер, и после $n-1$ фаз улучшать нечего.

Обратите внимание, что $n$ фаз, а не $n-1$: последняя фаза — это и есть проверка.

Петля отрицательного веса — тоже отрицательный цикл, и алгоритм её ловит без особых оговорок.

Первая строка содержит число $n$ ($1 \le n \le 100$).

Далее идут $n$ строк по $n$ чисел — матрица смежности. Веса по модулю меньше $10^5$; значение ровно $10^5$ означает отсутствие ребра.

Одно слово: YES или NO.