#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<cstdlib>
#include<random>
#define N 100000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,m,sz,ans,ans2,deg[N+1],st[N+1],leng,tong[N+1],length;
bool used[N+1],cl[N+1];
vector<int>E[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x),deg[x]++,deg[y]++;
	return;
}
int main()
{
	int x,y,cnt,rst;
	bool opt;
	T=read();
	while (T--)
	{
		n=read(),m=read(),opt=ans=ans2=sz=0;
		while (((1ll*sz*(sz+1))>>1)<=m) sz++;
		for (int i=1;i<=n;++i) E[i].clear(),deg[i]=cl[i]=0;
		for (int i=1;i<=m;++i) x=read(),y=read(),add(x,y);
		for (int i=0;i<=sz;++i)
		{
			length=rst=0;
			for (int j=1;j<=n;++j)
				if (deg[j]>=i)
					tong[++length]=j,rst+=deg[j];
			if (length==i)
			{
				cnt=0;
				for (int j=1;j<=length;++j)
					for (int k=0;k<E[tong[j]].size();++k)
						if (deg[E[tong[j]][k]]>=i)
							cnt++;
				if (cnt==length*(length-1)&&rst-((length*(length-1))>>1)==m)
				{
					opt=1,leng=length;
					for (int j=1;j<=leng;++j) st[j]=tong[j];
					break;
				}
			}
		}
		if (!opt)
		{
			for (int i=1;i<=n;++i)
				if (deg[i]<=sz-1)
				{
					cnt=rst=0;
					for (int j=0;j<E[i].size();++j) used[E[i][j]]=1,rst+=deg[E[i][j]];
					for (int j=0;j<E[i].size();++j)
						for (int k=0;k<E[E[i][j]].size();++k)
							cnt+=used[E[E[i][j]][k]];
					if (cnt==deg[i]*(deg[i]-1)&&rst-((deg[i]*(deg[i]-1))>>1)==m)
					{
						leng=0;
						for (int j=0;j<E[i].size();++j) used[E[i][j]]=0,st[++leng]=E[i][j];
						break;
					}
					for (int j=0;j<E[i].size();++j) used[E[i][j]]=0;
				}
		}
		for (int i=1;i<=leng;++i) cl[st[i]]=1;
		for (int i=1;i<=n;++i)
			if (!cl[i]&&deg[i]==leng)
				ans++;
		if (!ans)
		{
			ans=1;
			for (int i=1;i<=n;++i)
				if (!cl[i]&&deg[i]==leng-1)
					ans++;
		}
		for (int i=1;i<=n;++i)
			if (cl[i]&&deg[i]==leng-1)
				ans2++;
		if (!ans2)
		{
			ans2=1;
			for (int i=1;i<=n;++i)
				if (cl[i]&&deg[i]==leng)
					ans2++;
		}
		printf("%d %d\n",ans,ans2);
	}
	return 0;
}