#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
int N,M;
vector<int>G[1<<17];
int ex[1<<17];
bool inQ[1<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;
	for(;T--;)
	{
		cin>>N>>M;
		for(int i=0;i<N;i++)
		{
			G[i].clear();
			ex[i]=0;
			inQ[i]=false;
		}
		for(int i=0;i<M;i++)
		{
			int a,b;cin>>a>>b;
			a--,b--;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		vector<int>Vid(N);
		for(int i=0;i<N;i++)Vid[i]=i;
		sort(Vid.begin(),Vid.end(),[](int l,int r){return G[l].size()>G[r].size();});
		vector<int>Q;
		for(int u:Vid)if(ex[u]==Q.size())
		{
			Q.push_back(u);
			inQ[u]=true;
			for(int v:G[u])ex[v]++;
		}
		//cout<<"Qlique :";for(int u:Q)cout<<" "<<u+1;cout<<endl;
		{//Qlique
			int mxsize=Q.size(),cnt=1;
			for(int u=0;u<N;u++)if(!inQ[u])
			{
				int d=G[u].size();
				int nsz=Q.size();
				if(d==Q.size())nsz++;
				else if(d+1<Q.size())continue;
				if(mxsize<nsz)mxsize=nsz,cnt=0;
				if(mxsize==nsz)cnt++;
			}
			cout<<cnt<<" ";
		}
		{//Anti Qlique
			int mxsize=N-Q.size(),cnt=1;
			for(int u=0;u<N;u++)if(inQ[u])
			{
				int d=G[u].size();
				int nsz=N-Q.size();
				if(d+1==Q.size())nsz++;
				else if(d+1==Q.size()+1);
				else continue;
				if(mxsize<nsz)mxsize=nsz,cnt=0;
				if(mxsize==nsz)cnt++;
			}
			cout<<cnt<<"\n";
		}
	}
}