记录编号	334648	评测结果	AAAWWWAWWW
题目名称	951.MAX-2-SAT	最终得分	40
用户昵称	confoo	是否通过	未通过
代码语言	C++	运行时间	0.536 s
提交时间	2016-11-01 13:24:30	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#define file(x) "max2sat."#x
using std::max;
const int V=70,M=210;
inline int gid(int x,bool t){
	x<<=1;
	return x+t;
}
int n,m;
std::vector<int> to[V];
bool be[V];
std::stack<int> s;
void init(){
	for(int i=1;i<=n<<1;i++) to[i].clear();
}
void add(int x,int y){
	int f1=1,f2=1;
	if(x<0) x=-x,f1=0;
	if(y<0) y=-y,f2=0;
	x<<=1,y<<=1;
	to[(x+f1)^1].push_back(y+f2);
	to[(y+f2)^1].push_back(x+f1);
}
void rm(int x,int y){
	int f1=1,f2=1;
	if(x<0) x=-x,f1=0;
	if(y<0) y=-y,f2=0;
	x<<=1,y<<=1;
	to[(x+f1)^1].pop_back();
	to[(y+f2)^1].pop_back();
}
bool dfs(int u){
	if(be[u^1])  return false;
	else if(be[u]) return true;
	be[u]=1;
	s.push(u);
	for(int i=0;i<to[u].size();i++){
		int v=to[u][i];
		if(!dfs(v)) return false;
	}
	return true;
}
inline void clstk(){
	while(!s.empty()) s.pop();
}
inline void rec(){
	while(!s.empty()) be[s.top()]=0,s.pop();
}
bool sol(){
	memset(be,0,sizeof(be));
	for(int i=2;i<=n<<1;i+=2){
		if(be[i]||be[i^1]) continue;
		clstk();
		if(!dfs(i)){
			rec();
			if(!dfs(i^1)) return false;
		}
	}/*
	for(int i=1;i<=n;i++){
		if(be[gid(i,0)]) printf("0");
		else if(be[gid(i,1)]) printf("1");
		else printf("wa");
		printf(" ");
	}*/
	return true;
}
struct WD{
	int x,y;
}wd[M];
int fuse[M];
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		//init 
		init();
		int ans=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++) scanf("%d%d",&wd[i].x,&wd[i].y),fuse[i]=i;
		static const int SA=100;
		for(int i=1;i<=SA;i++){
			init();
			std::random_shuffle(fuse+1,fuse+1+m);
			int cnt=0;
			for(int i=1;i<=m;i++) {
				WD& now=wd[fuse[i]];
				add(now.x,now.y);
				if(sol()) ans=max(ans,++cnt);
				else rm(now.x,now.y);
			}
		}
		printf("%d\n",ans);
	}
}