Cliques

In graph theory, we call a subgraph of a undirected graph clique if each pair of nodes in it owns an edge between them. Consider a undirected graph G with n nodes. We hope to modify G into a new graph such that each connected component of it should be a clique. Each step of modification can be inserting a new edge or deleting an edge which has already existed.

The first line of the input contains an integer t which is the number of test cases. For each test case, the first line consists of an integer n (1 ≤ n ≤ 100) which is the number of nodes in undirected graph G. Each of the following n lines consists of n integers corresponding to the adjacency matrix of G where 1 represents the existence of the edge and 0 otherwise.

For each test case, output first the case number, see the sample output. There should be a space after the colon in each test case. Then, if the graph G can be modified into a new graph with no more than ten steps, output the minimum number of steps we need, or - 1 if not.

2
7
0 1 1 0 0 0 0
1 0 1 1 0 0 0
1 1 0 1 0 0 0
0 1 1 0 1 0 0
0 0 0 1 0 1 1
0 0 0 0 1 0 1
0 0 0 0 1 1 0
1
0

Case #1: 2
Case #2: 0

2016ACM/ICPC亚洲区青岛站-重现赛（感谢中国石油大学）