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