EduBrick

H. Дополнение графа

3000 мс · 256 МБ · всё или ничего

Дана матрица смежности простого неориентированного графа. Дополнением называется граф на тех же вершинах, в котором ребро есть тогда и только тогда, когда в исходном его не было. Петель ни там, ни там нет.

Выведите количество рёбер дополнения и его матрицу.

Проверка себя: сумма числа рёбер графа и его дополнения равна (n2)\dbinom{n}{2}.

Формат ввода

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

Далее идут nn строк по nn чисел — симметричная матрица с нулями на диагонали.

Формат вывода

В первой строке — число рёбер дополнения.

Далее nn строк по nn чисел — матрица дополнения.

Примеры

ввод
3
0 1 0
1 0 0
0 0 0
вывод
2
0 0 1
0 0 1
1 1 0
ввод
1
0
вывод
0
0
Войдите, чтобы отправлять решения.