Матриця мінімальних розрізів#5468

Матриця мінімальних розрізів

2 секунди

256 мегабайтів

Дуже складна

Вам задано зв'язний зважений граф $G$ . Мінімальним реберним розрізом між вершинами $u$ та $v$ назвемо множину $C_{u, v}$ C_{u,v} ребер з найменшою сумарною вагою, таку, що довільний шлях з $u$ в $v$ містить хоча б одне ребро з $C_{u, v}$ C_{u,v}. Позначимо величину мінімального розрізу між вершинами $u$ та $v$ як $c_{u, v}$ c_{u,v}.

Матрицю $c_{u, v}$ c_{u,v} назвемо матрицею мінімальних розрізів графа $G$ . Вам задано матрицю $c_{u, v}$ c_{u,v}. Знайдіть граф $G$ такий, що $c_{u, v}$ c_{u,v} - це матриця мінімальних розрізів цього графа чи визначте, що такого графа не існує.

Вхідні дані

У першому рядку вхідного файлу міститься число $n$ - розмір матриці ( $2 \leq n \leq 50$ 2 \leq n \leq 50). Наступні $n$ рядків містять по $n$ чисел кожен - елементи матриці. Гарантується, що матриця симетрична і містить лише нулі на головній діагоналі. Усі інші числа додатні і не перевищують $1000$ .

Вихідні дані

Якщо існує граф $G$ , для якого матриця з вхідного файлу - матриця мінімальних розрізів, напишіть у першому рядку вихідного файлу YES. У другому рядку виведіть $m$ - число ребер графа. Далі, у $m$ рядках виведіть опис ребер графа. Кожне ребро задається початковою вершиною $u_{i}$ u_i, кінцевою вершиною $v_{i}$ v_i та вагою ребра між вершинами $u_{i}$ u_i та $v_{i}$ v_i. У графі не повинно бути петель, паралельних дуг. Вага кожного ребра не повинна перевищувати $1000$ .

Якщо графа, який задовольняє умові, не існує, виведіть у єдиному рядку вихідного файлу NO.

Приклади

Приклад 1