//Author: Kevin5307
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int u[100100],v[100100];
vector<int> G[100100],con[100100];
bool flag[100100];
int deg[100100];
int near[100100];
void update(pii &a,int val)
{
	if(a.first==val)
		a.second++;
	if(a.first<val)
		a=mp(val,1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			G[i].clear();
			con[i].clear();
			deg[i]=near[i]=flag[i]=0;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>u[i]>>v[i];
			deg[u[i]]++;
			deg[v[i]]++;
			G[u[i]].pb(v[i]);
			G[v[i]].pb(u[i]);
		}
		int cnt=0;
		vector<int> vec;
		for(int i=1;i<=n;i++)
			vec.pb(i);
		sort(ALL(vec),[&](const int &a,const int &b){return deg[a]>deg[b];});
		for(auto i:vec)
		{
			if(sz(G[i])<cnt)
			{
				flag[i]=0;
				continue;
			}
			int c=0;
			for(auto x:G[i])
				if(flag[x])
					c++;
			flag[i]=(c==cnt);
			cnt+=flag[i];
		}
		int count=0;
		for(int i=1;i<=m;i++)
			if(!flag[u[i]]&&!flag[v[i]])
				count++;
		if(count)
		{
			ll sm=0;
			for(int i=1;i<=n;i++)
				if(flag[i])
					sm+=i;
			for(int i=1;i<=n;i++)
			{
				ll sum=0;
				for(auto j:G[i])
					if(flag[j])
					{
						near[i]++;
						sum+=j;
					}
				if(near[i]==cnt-1)
					con[sm-sum].pb(i);
			}
			for(int i=1;i<=n;i++)
				if(flag[i])
				{
					int change=0;
					for(auto x:con[i])
					{
						for(auto y:G[x])
							if(!flag[y])
								change++;
						flag[x]=1;
					}
					if(change==count)
					{
						bool fl=1;
						for(auto j:G[i])
							if(!flag[j])
							{
								fl=0;
								break;
							}
						if(fl)
						{
							flag[i]=0;
							break;
						}
					}
					for(auto x:con[i])
						flag[x]=0;
				}
		}
		pii ans1=mp(-1,0),ans2=mp(-1,0);
		int c1=0,c2=0;
		for(int i=1;i<=n;i++)
			if(flag[i])
				c1++;
			else
				c2++;
		update(ans1,c1);
		update(ans2,c2);
		for(int i=1;i<=n;i++)
			if(!flag[i])
			{
				int indeg=0;
				for(auto j:G[i])
					if(flag[j])
						indeg++;
				update(ans1,indeg+1);
			}
		for(int i=1;i<=n;i++)
			if(flag[i])
			{
				int indeg=c2;
				for(auto j:G[i])
					if(!flag[j])
						indeg--;
				update(ans2,indeg+1);
			}
		cout<<ans1.second<<" "<<ans2.second<<'\n';
	}
	return 0;
}