davidwang's Blog

第一问： 网络流，这并没有什么问题

第二问： 阿丽和桃子的游戏，这并没有什么问题

总之是傻逼了

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 210;
struct edge{
	int to,flow;
	edge(int to=0,int flow=0): to(to),flow(flow){}
}e[N*N*2];
int d[N],f[N*N*2],x[N],n,m,cnt,q[N];
vector<int>g[N];
bitset<N*N>A;
inline void connect(int a,int b,int f){
	e[cnt]=edge(b,f);
	g[a].push_back(cnt++);
	x[a]++;
	e[cnt]=edge(a,f);
	g[b].push_back(cnt++);
	x[b]++;
}
int s=1,t=2;
inline int bfs()
{
	int head=0,tail=1,u,v;
	for (int i=1;i<=n;i++) d[i]=0;
	d[s]=1; q[1]=s;
	while (head<tail){
		u=q[++head];
		for (vector<int>::iterator it=g[u].begin();it!=g[u].end();it++){
			if (e[*it].flow && !d[e[*it].to]){
				q[++tail]=e[*it].to;
				d[e[*it].to]=d[u]+1;
			}
		}
	}
	return d[t];
}
inline int dfs(int x,int flow){
	if (x==t || flow==0) return flow;
	int totflow=0,f;
	for (vector<int>::iterator it=g[x].begin();it!=g[x].end();it++){
		if (e[*it].flow && d[e[*it].to]==d[x]+1){
			f=dfs(e[*it].to,min(flow,e[*it].flow));
			flow-=f; totflow+=f;
			e[*it].flow-=f; e[(*it)^1].flow+=f;
			if (flow==0) return totflow;
		}
	}
	if (flow) d[x]=-1;
	return totflow;
}
inline void work()
{
	int ans1=0,ans2=0;
	n=read(); m=read();
	cnt=0;
	for (int i=1;i<=n;i++){
		g[i].clear();
		x[i]=0;
	}
	int cE=m; 
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		if (x+y==3) cE--;
		else connect(x,y,1);
	}
	for (int i=0;i<=m*2;i++) A[i]=0;
	A[x[1]]=1;
	while (bfs()) ans1+=dfs(s,INT_MAX);
	printf("%d ",cE-ans1);
	for (int i=3;i<=n;i++){
		A=(A<<x[i]|A);
	}
	for (int i=0;i<=cE;i++){
		if (A[cE+i]==1 || A[cE-i]==1){
			printf("%d\n",i);
			break;
		}
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int T=read();
	while (T--) work();
	return 0;
}