Minimum Cut Matrix#5468
Consider a connected weighted undirected graph . A minimum edge cut between vertices and is the set C_{u,v} of edges with minimal total weight, such that each path from to contains at least one edge from C_{u,v}. Let us denote the weight of a minimum edge cut between vertices and as c_{u,v}.
The matrix c_{u,v} is called the minimum cut matrix of graph . You are given a matrix c_{u,v}. Find the graph such that c_{u,v} is the minimum cut matrix of this graph, or detect that there is no such graph.
The first line of the input file contains - the size of the matrix (2 \leq n \leq 50). The following lines contain 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 .
If there exists a graph such that the matrix in the input file is its minimum cut matrix, print YES at the first line of the output file. In this case print - the number of edges in the graph at the second line, and describe edges in the following lines. Each edge must be described by the numbers of vertices it connects u_i, v_i, and the weight of the edge between vertices u_i and v_i. There must be no loops, neither parallel edges. No weight must exceed .
If there is no such graph, print NO at the first line of the output file.
Example 1