完全多部图的DRC圈覆盖的任务书.docx

完全多部图的DRC圈覆盖的任务书
任务描述：
给定一个包含n个节点、m条边的完全多部图，其中每个部分内的节点之间没有边相连，要求在这个完全多部图中，找到最小的圈（环），使得每个部分内都至少覆盖了一个圈。
输入：
第一行，一个正整数T，表示测试数据组数。
每组测试数据输入如下：
第一行两个整数n,m，表示该完全多部图的节点个数和边个数。
接下来m行，每行两个整数u,v（1≤u,v≤n），表示一条边。
输出：
对于每组测试数据，输出一行一个整数，表示求解的最小圈的大小。若不存在符合要求的圈，则输出-1。
示例：
输入：
2
615
12
13
23
14
24
34
15
25
35
45
16
26
36
46
56
55
12
13
14
15
23
输出：
4
-1
提示：
第一个样例中，图形如下：
```
1-2
|/|
3-4
|/|
5-6
```
如果选取1-2-3-1和4-3-2-4两个圈，1、2、3、4部分都被覆盖了，圈大小为4。
第二个样例中，1、2、3、4部分无法通过圈来覆盖，因此无解，输出-1。