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