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

Матрица минимальных разрезов

2 секунды
256 мегабайт
Very hard

Вам дан связный взвешенный граф . Минимальным рёберным разрезом между вершинами и назовём множество C_{u,v} рёбер с наименьшим суммарным весом, такое, что любой путь из в содержит хотя бы одно ребро из C_{u,v}. Обозначим величину минимального разреза между вершинами и за c_{u,v}.

Матрицу c_{u,v} назовём матрицей минимальных разрезов графа . Вам дана матрица c_{u,v}. Найдите граф такой, что c_{u,v} - это матрица минимальных разрезов этого графа или определите, что такого графа не существует.

Input

В первой строке входного файла содержится число - размер матрицы (2 \leq n \leq 50). Следующие строк содержат по чисел каждая - элементы матрицы. Гарантируется, что матрица симметрична и содержит только нули на главной диагонали. Все остальные числа положительные и не превосходят .

Output

Если существует граф , для которого матрица из входного файла - матрица минимальных разрезов, напишите в первой строке выходного файла YES. Во второй строке выведите - число рёбер графа. Далее, в строках выведите описание рёбер графа. Каждое ребро задаётся начальной вершиной u_i, конечной вершиной v_i и весом ребра между вершинами u_i и v_i. В графе не должно быть петель, параллельных дуг. Вес каждого ребра не должен превышать .

Если графа, удовлетворяющего условию, не существует, выведите в единственной строке выходного файла NO.

Examples

Example 1

Loading
Loading