Матриця мінімальних розрізів
Вам задано зв'язний зважений граф 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.