Task
Time limit:
1000 ms,
Memory limit:
256 Mb
Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
Входные данные
В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.
Выходные данные
В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то выведите любой из них.
|
Ввод |
Вывод |
|
3
100000 100000 -51
100 100000 100000
100000 -50 100000
|
YES
4
3 2 1 3
|