Матрица минимальных разрезов
Consider a connected weighed undirected graph G. A minimal edge cut between vertices u and v is the set C_{u,v} of edges with minimal total weight, such that each path from u to v contains at least one edge from C_{u, v}. Let us denote the weight of a minimal edge cut between vertices u and v as c_{u,v}.
The matrix c_{u,v} is called the minimal cut matrix of graph G. You are given a matrix c_{u,v}. Find the graph G such that c_{u,v} is the minimal cut matrix of this graph, or detect that there is no such graph.
Input
The first line of the input file contains n - the size of the matrix (2 ≤ n ≤ 50). The following n lines contain n integer numbers each - the entries of the matrix. It is guaranteed that the matrix is symmetric and has zeroes at the main diagonal. All other entries are positive and do not exceed 1000.
Output
If there exists a graph G such that the matrix in the input file is its minimal cut matrix, print YES at the first line of the output file. In this case print m - the number of edges in the graph at the second line, and describe edges in the following m lines. Each edge must be described by the numbers of vertices it connects, and the weight of the corresponding edge. There must be no loops, neither parallel edges. No weight must exceed 1000.
If there is no such graph, print NO at the first line of the output file.