记录编号	337074	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.587 s
提交时间	2016-11-03 21:18:16	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=15;
int cnt[N];
int DFS(int d=0){
  int flag=0,ret=100;
  for(int i=0;i<=14;i++)
    if(cnt[i])flag=1;
  if(!flag)return 0;
  for(int i=3;i<=10;i++){
    flag=1;
    for(int j=i;j<=i+3;j++)if(!cnt[j])flag=0;
    if(!flag)continue;
    for(int j=i;j<=i+3;j++)cnt[j]-=1;
    for(int j=i+4;j<=15;j++){
      if(cnt[j]){cnt[j]-=1;ret=min(ret,DFS()+1);}
      else{for(int k=j-1;k>=i;k--)cnt[k]+=1;break;}
    }
  }
  
  for(int i=3;i<=12;i++){
    flag=1;
    for(int j=i;j<=i+1;j++)if(cnt[j]<2)flag=0;
    if(!flag)continue;
    for(int j=i;j<=i+1;j++)cnt[j]-=2;
    for(int j=i+2;j<=15;j++){
	  if(cnt[j]>=2){cnt[j]-=2;ret=min(ret,DFS()+1);}
      else{for(int k=j-1;k>=i;k--)cnt[k]+=2;break;}
    }
  }

  for(int i=3;i<=13;i++){
    flag=1;
    for(int j=i;j<=i;j++)if(cnt[j]<3)flag=0;
    if(!flag)continue;
    for(int j=i;j<=i;j++)cnt[j]-=3;
    for(int j=i+1;j<=15;j++){
      if(cnt[j]>=3){cnt[j]-=3;ret=min(ret,DFS()+1);}
      else{for(int k=j-1;k>=i;k--)cnt[k]+=3;break;}
    }
  }
  
  //三带一 三带二
  for(int i=0;i<=14;i++){
    if(cnt[i]<3)continue;
	cnt[i]-=3;
    for(int j=1;j<=14;j++){
      if(i==j)continue;
      if(cnt[j]>=2){cnt[j]-=2;ret=min(ret,DFS()+1);cnt[j]+=2;}
      if(cnt[j]){cnt[j]-=1;ret=min(ret,DFS()+1);cnt[j]+=1;}
    }
    cnt[i]+=3;
  }

  for(int i=0;i<=14;i++){
    if(cnt[i]<4)continue;
    cnt[i]-=4;
    for(int j=1;j<=14;j++)if(i!=j&&cnt[j]>1)
	for(int k=j+1;k<=14;k++)if(i!=k&&cnt[k]>1)
	  {cnt[j]-=2;cnt[k]-=2;ret=min(ret,DFS()+1);cnt[j]+=2;cnt[k]+=2;}

    for(int j=1;j<=14;j++)if(i!=j&&cnt[j])
	for(int k=j+1;k<=14;k++)if(i!=k&&cnt[k])
	  {cnt[j]-=1;cnt[k]-=1;ret=min(ret,DFS()+1);cnt[j]+=1;cnt[k]+=1;}
	cnt[i]+=4;
  }
  flag=0;
  for(int i=0;i<=14;i++)if(cnt[i])flag+=1;
  return min(ret,flag);
}
int T,n;
int main(){
	freopen("landlords.in","r",stdin);
	freopen("landlords.out","w",stdout);
  scanf("%d%d",&T,&n);
  while(T--){
    memset(cnt,0,sizeof(cnt));
    for(int i=1,a,b;i<=n;i++){
      scanf("%d%d",&a,&b);
      cnt[a]+=1;
    }
    cnt[14]=cnt[1];cnt[1]=0;
    printf("%d\n",DFS(1));
  }
  return 0;
}