//prepare for coding{{{
#include<bits/stdc++.h>

//#define RELEASE
#ifndef RELEASE
#define FL
#define DB(...) fprintf(stderr,__VA_ARGS__)
#endif 

using namespace std;

const int N=100000,M=100000;

inline int Read(){
	char c=getchar();
	int res=0;
	bool b=0;
	while(c>'9'||c<'0')
		b=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')
		res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return b?-res:res;
}

int n,m;
int px[N+10];
//}}}

//graph{{{
int head[N+10],te;
int deg[N+10],dt[N+10];
bool ok[N+10];
int cl[N+10];

struct EDGE{
	int n,t;
}e[N*2+10];

inline void Adde(int u,int v){
	++deg[u],++deg[v];
	e[++te].n=head[u];
	e[te].t=v;
	head[u]=te;
	e[++te].n=head[v];
	e[te].t=u;
	head[v]=te;
}
//}}}

//solve{{{
inline bool Cmp(int a,int b){
	return deg[a]>deg[b];
}
inline void Solve(){
	n=Read(),m=Read();
	te=0;
	for(int i=1;i<=n;++i)
		deg[i]=dt[i]=head[i]=cl[i]=ok[i]=0;
	for(int i=1;i<=m;++i)
		Adde(Read(),Read());
	for(int i=1;i<=n;++i)
		px[i]=i;
	sort(px+1,px+1+n,Cmp);
	int yz=0,ss=0;
	for(int i=1;i<=n;++i){
		int u=px[i];
		for(int ie=head[u],v=e[ie].t;ie;ie=e[ie].n,v=e[ie].t)
			if(ok[v])
				++dt[u];
		if(dt[u]==i-1)
			ok[u]=1;
		else{
			yz=deg[u];
			break;
		}
	}
	for(int u=1;u<=n;++u)
		if(deg[u]>yz)
			++ss;
	int ans1=0,ans2=0;
	for(int u=1;u<=n;++u)
		if(deg[u]==yz&&deg[u]==ss)
				++ans1;
	if(!ans1){
		ans1=1;
		for(int i=1;i<=n;++i)
			if(deg[i]<=yz&&deg[i]==ss-1)
				++ans1;
		for(int u=1;u<=n;++u)
			if(deg[u]<=yz)
				for(int ie=head[u],v=e[ie].t;ie;ie=e[ie].n,v=e[ie].t)
					if(ok[v])
						++cl[v];
		for(int u=1;u<=n;++u)
			if(deg[u]>yz&&!cl[u])
				++ans2;
		if(!ans2){
			ans2=1;
			for(int u=1;u<=n;++u)
				if(deg[u]<=yz)
					for(int ie=head[u],v=e[ie].t;ie;ie=e[ie].n,v=e[ie].t)
						if(cl[v]==1)
							++ans2;
		}
		printf("%d %d\n",ans1,ans2);
	}
	else{
		if(ans1>1)
			ans2=1;
		else{
			ans2=1;
			for(int u=1;u<=n;++u)
				if(deg[u]==yz&&dt[u]==ss)
					ok[u]=1;
			for(int u=1;u<=n;++u)
				if(deg[u]<=yz)
					for(int ie=head[u],v=e[ie].t;ie;ie=e[ie].n,v=e[ie].t)
						if(ok[v])
							cl[v]=1;
			for(int u=1;u<=n;++u)
				if(deg[u]>yz&&!cl[u])
					++ans2;
		}
		printf("%d %d\n",ans1,ans2);
	}
}
//}}}

//main{{{
int main(){
	int T=Read()+1;
	while(--T)
		Solve();
	return 0;
}
//}}}
//《象》曰：泽灭木，大过。君子以独立不惧，遁世无