#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+9;
LL n,m;
LL d[N];
template<typename T>
inline void read(T &x)
{
	x=0;T w=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;	c=getchar();}
	while(isdigit(c)){x=x*10+(c^'0');	c=getchar();}
	if(w==-1)	x=-x;
}
template<typename T,typename... Args>
inline void read(T &x,Args &...args)
{
	read(x),read(args...);
}
LL calc()
{
	sort(d+1,d+n+1,greater<LL>());
	LL a,ans=1;
	for(LL i=n;i>=1;--i)
	{
		if(d[i]>=i-1)
		{
			a=i;
			break;
		}
	}
	for(LL i=a+1;i<=n;++i)
		if(d[i]==a-1)	++ans;
	return ans;
}
void solve()
{
	read(n,m);
	for(LL i=1;i<=n;++i)
		d[i]=0;
	for(LL i=1,u,v;i<=m;++i)
	{
		read(u,v);
		++d[u],++d[v];
	}
	LL ans1=calc();
	for(LL i=1;i<=n;++i)
		d[i]=n-1-d[i];
	LL ans2=calc();
	printf("%lld %lld\n",ans1,ans2);
}
int main()
{
	LL T;
	read(T);
	while(T--)	solve();
	return 0;
}