记录编号	341243	评测结果	AAAAAAAAAW
题目名称	MAX-2-SAT	最终得分	90
用户昵称	confoo	是否通过	未通过
代码语言	C++	运行时间	3.673 s
提交时间	2016-11-07 15:50:10	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<ctime> 
#include<cstdlib>
#define file(x) "max2sat."#x
using std::max;
using std::min;
const int V=70,M=210;
int n,m,hed[V],nxt[M<<1],sz;
struct EDGE{int u,v;}st[M<<1];
bool be[V];
struct STK{int st[V],sz;
inline int top(){return st[sz];}
inline bool empty(){return !sz;}
inline void pop(){--sz;}
inline void push(int x){st[++sz]=x;}
}stk;
//std::stack<int> stk;
void init(){
	memset(hed,0,sizeof(hed));
	sz=0;
}
void add(int u,int v){
	st[++sz].u=u;st[sz].v=v;
	nxt[sz]=hed[u],hed[u]=sz;
}
void rm(int u){
	hed[u]=nxt[hed[u]];
}
void addwd(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;
	add((x+f1)^1,y+f2);
	add((y+f2)^1,x+f1);
}
void rmwd(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;
	rm((x+f1)^1);
	rm((y+f2)^1);
}
namespace Tarjan{
	//STK stk;
	bool f=0;
	int dfn[V],dfsclk,scnt,scid[V];
	int dfs(int u){
		if(f) return 0;
		stk.push(u);
		int lowu=dfn[u]=++dfsclk;
		for(int e=hed[u];e;e=nxt[e]){
			int v=st[e].v;
			if(!dfn[v]) lowu=min(lowu,dfs(v));
			else if(!scid[v]) lowu=min(lowu,dfn[v]);
			if(f) return 0;
		}
		if(dfn[u]==lowu){
			++scnt;
			int x;
			do{
				x=stk.top();stk.pop();
				scid[x]=scnt;
				if(scid[x^1]==scid[x]) {
					f=1;
					return 0;
				}
			}while(x!=u);
		}
		return lowu;
	}
	bool go(){
		f=0;
		stk.sz=0;
		memset(scid,0,sizeof(scid));
		dfsclk=scnt=0;
		memset(dfn,0,sizeof(dfn));
		for(int i=1;i<=(n<<1)+1;i++) if(!dfn[i]) {
			dfs(i);
			if(f) return false;
		}
		for(int i=2;i<=(n<<1)+1;i+=2) if(scid[i]==scid[i^1]) return false;
		return true;
	}
}
struct WD{
	int x,y;
}wd[M];
int fuse[M];
int main(){
	srand(time(NULL));
	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=800;
		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]];
				addwd(now.x,now.y);
				if(Tarjan::go()) ans=max(ans,++cnt);
				else rmwd(now.x,now.y);
			}
		}
		printf("%d\n",ans);
	}
}