Дан ориентированный граф. Требуется определить: есть ли в нем цикл отрицательного веса? И если да, то вывести его.
В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 105. Если ребра нет, соответствующее значение равно 105.
В выходной файл OUTPUT.TXT выведите «YES», если цикл существует, или «NO», в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то выведите любой из них.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
100000 100000 -51
100 100000 100000
100000 -50 100000 | YES
4
3 2 1 3 |
