题目：

(https://ac.nowcoder.com/acm/problem/14122)

古往今来的各种传说中存在着很多魔法阵，它们的激活方式也各不相同。传说在北师大电子楼前的小花园里就有一个魔法阵，上次出现还是在很多很多很多年前，但是现在它又出现了！ 这时，小Q同学面无表情地说：“传说这个魔法阵都会在都会在来自远古的恶魔Awesome Crystal Monster（ACM）降临的时候出现，现在，这个时候终于要到来了吗！”话音未落，小Q同学已经走到了魔法阵前，取出一个小瓶，开始用瓶中的圣水激活这个魔法阵，“你们快退后，这里就交给我了！” 这个魔法阵由一些点和一些连接这些点的边构成，当小Q同学把圣水滴在一个点上时，和这个点相连的所有边就会被点亮并发出神圣的光芒，当魔法阵所有的边都点亮的时候，就会出现强大的神圣力量。但是小Q同学拥有的圣水非常有限，只有10滴，现在小Q同学想知道他最少可以用多少滴圣水点亮整个魔法阵，如果耗尽圣水也不能点亮，就只能打出一波GG了。

输入描述:

第一行包含一个正整数T(≤ 20)，表示测试数据的组数， 对于每组测试数据， 第一行是两个整数n(1 ≤ n ≤ 1000)和m(1 ≤ m ≤ 2000)，表示魔法阵的点数和边数， 接下来m行，每行包含两个整数u,v(1 ≤ u,v ≤ n)，表示有一条边连接了u号点和v号点。

输出描述:

对于每组测试数据，如果使用不超过10滴圣水可以点亮整个魔法阵，输出最少需要的圣水滴数，否则输出"GG"（不含引号）。 分析&回顾：

　　首先，这道题我又没做出来（哎，被自己菜到了，加油！）。一开始我想这只是存个图，然后遍历点，所以我用的是Bfs，但发现用Bfs时没有明确的起点、终点，貌似拓展不起来~接着，我就想直接统计每个点的临边数，从大到小排序，然后依次滴，But这个思路刚冒出就打消了，因为尽管有些点的连通边多，但可能之前的药水其实会影响它的“有效”连通边。

　　其实，这道题有些类似下棋，赢得方法就是尽快铺满棋盘。对于这种起点、终点不确定的找最优解的搜索应该用Dfs，找到每种点滴方法的结果并筛选。因为，连通的点，相互影响，更好的方法是遍历边，边只要其中一个端点被滴到，那么这条边就相当于被遍历过（这个思路是在其他博客看到的，好巧妙啊~）。可以自己画个草图试试，这样子理解更深。

　　结构体来存储每条边的两个端点，vis数组标记被点滴到的点（间接反映哪些边被标记），Dfs从任意一边开始都行（就直接按照题目输入的顺序了），不需要遍历循环来假设某个边为起始（DFS主要利用迭代，若再加上循环复杂度会很大，尽量避开:BFS-循环，DFS-迭代）。

　　这是我自己画的一个图，假设自己在DFS取最优：

OK，上代码：

1 #include 
     
          //遍历边 2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=1000,maxm=2000,Judge=10; 6 const int Inf=0x7fffffff; 7 struct Node{ 8     int x,y; 9 }node[maxm];//存无向边10 bool vis[maxn]={
   0};//标记点11 bool judge[maxm]={
   0};//标记边12 int n=0,m=0,ans=Inf;13 void Dfs(int sum,int cnt)// 覆盖的边数，使用的圣水数14 {15     if(cnt>Judge) return ;//超限，剪枝16     if(sum==m){
   //完全覆盖17         ans=min(ans,cnt);18         return ;19     }20     if(vis[node[sum].x]==1||vis[node[sum].y]==1){
   //端点被访问21             Dfs(sum+1,cnt);22     }23     else{
   //任取其中一个端点，滴圣水24         vis[node[sum].x]=1;25         Dfs(sum+1,cnt+1);26         vis[node[sum].x]=0;27             28         vis[node[sum].y]=1;29         Dfs(sum+1,cnt+1);30         vis[node[sum].y]=0;31     }    32     return;33 }34 int main()35 {36     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //解绑,提高效率37     int t;38     cin>>t;39     while(t--)40     {41         memset(vis,0,sizeof(vis));42         memset(judge,0,sizeof(judge));43         ans=Inf;44         cin>>n>>m;45         for(int i=0;i
        
         >node[i].x>>node[i].y;//存储边47         Dfs(0,0);48         if(ans<=10) cout<
         
          <