#include <bits/stdc++.h>

using namespace std;

static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
template<typename item>
inline void read(register item &x)
{
	bool flag=false;
    x=0;register char c=getchar();
    while(c<'0'||c>'9')
	{
		if(c=='-')
		flag=true;
		c=getchar();
	}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(flag)
    x=-x;
}

const int MAXN=1e5+50;

int N,M;
int Deg[MAXN],Cnt[MAXN];
int a[MAXN],tot;
void Solve()
{
	read(N);
	read(M);
	if(M==0)
	{
		printf("%d %d\n",N,1);
		return;
	}
	for(int i=1;i<=N;i++)
	Deg[i]=0; 
	for(int i=1;i<=M;i++)
	{
		int x,y;
		read(x);
		read(y);
		Deg[x]++;
		Deg[y]++;
	}
	for(int i=1;i<=N;i++)
	{
		Cnt[Deg[i]]++;
	}
	tot=0;
	for(int i=N;i>=0;i--)
	{
		while(Cnt[i])
		{
			a[++tot]=i;
			Cnt[i]--;
		}
	}
	int Size=0;
	for(int i=1;i<=N;i++)
	{
		if(a[i]>=Size)
		{
			Size++;
		}
		else
		break;
	}
	
	int ans1=1,ans2=0;
	for(int i=Size+1;i<=N;i++)
	{
		if(a[i]==Size-1)
		ans1++;
		else
		break;
	}
	if(a[Size]<=Size)
	{
		ans2=(a[Size]==Size);
		for(int i=Size;i>=1;i--)
		{
			if(a[i]==a[Size])
			ans2++;
			else
			break;
		}
	}
	else
	ans2=1;
	printf("%d %d\n",ans1,ans2);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		Solve();
	}
}
/*
stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* i and j are misplaced
	* variable misuse
	* do smth instead of nothing and stay organized
	* vector cause MLE or TLE
	* wrong file name
	* DON'T SLEEP IN THE EXAM
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
	* DON'T GET A SWELLED HEAD
	* YOU MUSTN'T HAVE EMOTION
->be based on Benq's code
*/