思路：

先搜索出来如果选这个点 其它哪些点必须选

跑个背包就好了

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 66666int xx,yy,v[N],next[N],first[1004],tot,top,vis[1004],cases,m,r,f[1005][1005];struct Stk{int x,y;}s[N];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){    if(x<=m)s[top].x++;    else s[top].y++;    for(int i=first[x];~i;i=next[i])        if(!vis[v[i]])            vis[v[i]]=1,dfs(v[i]);}int main(){    scanf("%d",&cases);    while(cases--){
             memset(f,0,sizeof(f));        memset(vis,0,sizeof(vis));        memset(first,-1,sizeof(first));        tot=top=0;        scanf("%d%d",&m,&r);        while(r--)scanf("%d%d",&xx,&yy),add(xx,yy+m),add(yy+m,xx);        for(int i=1;i<=m*2;i++)            if(!vis[i])                vis[i]=1,top++,s[top].x=s[top].y=0,dfs(i);        f[0][0]=1;        for(int i=1;i<=top;i++)            for(int j=m;j>=s[i].x;j--)                for(int k=m;k>=s[i].y;k--)                    f[j][k]=f[j][k]|f[j-s[i].x][k-s[i].y];        for(int i=m/2;i>=0;i--)            if(f[i][i]){
                     printf("%d\n",i);                break;            }    }}