题号：NC19045
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
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.
示例1
输入
复制
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