Задачи
Матрица минимальных разрезов
Матрица минимальных разрезов
Вам дан связный взвешенный граф \textbf{G}. \textit{Минимальным рёберным разрезом} между вершинами \textbf{u} \textbf{v} назовём множество \textbf{C_\{u,v\}} рёбер с наименьшим суммарным весом, такой, что любой путь из \textbf{u} в \textbf{v} содержит хотя бы одно ребро из \textbf{C_\{u,v\}}. Обозначим величину минимального разреза между вершинами \textbf{u} и \textbf{v} за \textbf{c_\{u,v\}}.
Матрицу \textbf{c_\{u,v\}} назовём \textit{матрицей минимальных разрезов} графа \textbf{G}. Вам дана матрица \textbf{c_\{u,v\}}. Найдите граф \textbf{G} такой, что \textbf{c_\{u,v\}} - это матрица минимальных разрезов этого графа или определите, что такого графа не существует.
\InputFile
В первой строке входного файла содержится число \textbf{n} - размер матрицы (\textbf{2} ≤ \textbf{n} ≤ \textbf{50}). Следующие \textbf{n} строк содержат по \textbf{n} чисел каждая - элементы матрицы. Гарантируется, что матрица симметрична и содержит только нули на главной диагонали. Все остальные числа положительные и не превосходят \textbf{1000}.
\OutputFile
Если существует граф \textbf{G}, для которого матрица из входного файла - матрица минимальных разрезов, напишите в первой строке выходного файла \textbf{YES}. Во второй строке выведите \textbf{M} - число рёбер графа. Далее, в \textbf{m} строках выведите описание рёбер графа. Каждое ребро \textbf{i} задаётся начальной вершиной \textbf{u_i}, конечной вершиной \textbf{v_i} и весом ребра между вершинами \textbf{u_i} и \textbf{v_i}. В графе не должно быть петель, параллельных дуг. Вес каждого ребра не должен превышать \textbf{1000}.
Если графа, удовлетворяющего условию, не существует, выведите в единственной строке выходного файла \textbf{NO}.
Входные данные #1
3 0 2 2 2 0 2 2 2 0
Выходные данные #1
YES 2 1 2 2 1 3 2