18645번 - Graph Measurement 스페셜 저지다국어

Andrew has a simple (no loops or multiple edges) undirected graph on n vertices (1 ≤ n ≤ 20). He repeats the following measurement k times: for each edge of the graph, independently color it black or white (50% probability for each color). Then he counts the number of black edges adjacent to each vertex, and tells these n numbers to you.

Your goal is to restore the original graph given these k · n numbers.

The first line of the input contains two integers n and k (1 ≤ n ≤ 20, in all cases except the sample input k = 800 · n²). The next k lines contain n integers each, denoting the number of black edges adjacent to each vertex in the corresponding measurement. The vertices are numbered from 1 to n, and the values in each line are given in the order of vertex numbers.

In the first line of the output print an integer m — the number of edges in the graph you think was used to generate the input. In the next m lines describe the edges. Each edge should be described by the two numbers of vertices it connects. The vertices are numbered from 1 to n, there must be no edges connecting a vertex to itself, and at most one edge for any given pair of vertices.

In the sample case, any valid graph will be accepted, even if it’s not consistent with the input (for example a graph with 0 edges will be accepted). In all cases except the sample case, only the graph that was actually used to generate the input will be accepted.

The order of printing the edges, and the order of printing the two vertices within each edge do not matter, you may use any.

Note that all cases except the sample case have a lot of measurements — more precisely, k = 800 · n².

In the sample input and output above, both edges were colored black for the first measurement, and only the first edge was colored black for the second measurement.

There are 33 non-sample test cases in this problem.