графы

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в i-й строке и j-м столбце находится 1, если от вершины i можно добраться до вершины j, и 0 - иначе.

 

Входные данные

В первой строке дано число N (1<=N<=100) - число вершин в графе. Далее задана матрица смежности графа: в N строках даны по N чисел 0 или 1 в каждой. i-е число в i-й строке всегда равно 1.

 

Выходные данные

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Ввод	Вывод
4 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1	1 1 1 0  1 1 1 0  1 1 1 0  1 1 1 1

Дан связный ориентированный невзвешенный граф. Требуется вывести номера вершин из которых исходят все его обратные ребра (нумерация с 1).

 

Входные данные:

Целое число n и m - число вершин и ребер в графе.

Следующие m строк содержат 2 числа a и b, показывающие, что из вершины a есть ребро в вершину b.

 

Выходные данные:

В первой строке должно находиться число n - количество обратных ребер, в следующей строке должны быть перечисленны вершины в порядке возрастания без повторений. Если обратных ребер нет, тогда следует вывести -1.