题目大意

N个人，M组关系，每次选一种关系，如果两个人相邻，则任意删除其中一个，否则不变。问最坏情况下最多能剩多少人。

分析

为了留的人最多，我们可以先将原来不相邻的关系全部说完，这样我们只需要考虑以怎样的顺序说剩下的那些即可。由于剩下的关系可能被分成一段一段的，所以我们只需要预处理在一个均相连的区间内有k个人最坏情况最多剩下多少人即可。经过考虑我们发现从中间将这一组关系分成两段可以使结果最优，所以我们就得到了递推式子，详见代码。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include