// created:  Sep/02/2023 21:30:20
#include<cstdio>
#include<vector>
#include<algorithm>
#include<random>
#include<chrono>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
using namespace std;
template<typename T>void readmain(T &x)
{
	bool neg=false;
	unsigned int c=getchar();
	for(;(c^48)>9;c=getchar())if(c=='-')neg=true;
	for(x=0;(c^48)<10;c=getchar())x=(x<<3)+(x<<1)+(c^48);
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
constexpr int N=1e5+5;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
int tt,n,m,deg[N],id[N];
bool tg[N],ok[N],in[N];
ull w[N],sum[N];
vector<int> adj[N];
int main()
{
	read(tt);
	while(tt--)
	{
		read(n,m);
		F(i,0,m)
		{
			int u,v;read(u,v);--u,--v;
			adj[u].emplace_back(v);
			adj[v].emplace_back(u);
		}
		F(i,0,n)deg[i]=(int)adj[i].size(),id[i]=i;
		sort(id,id+n,[](int u,int v){return deg[u]>deg[v];});
		F(i,0,n)tg[i]=false;
		int mx=0;
		F(i,0,n)
		{
			int u=id[i],cnt=0;
			for(int v:adj[u])cnt+=tg[v];
			if(cnt!=i)break;
			mx=max(mx,i+1);
			tg[u]=true;
		}
		deg[n]=0;
		F(i,0,n)w[i]=rnd();
		if(mx<n&&deg[id[mx]]>=mx)
		{
			int l=0,r=0,siz=deg[id[mx]]+1;
			while(deg[id[l]]>deg[id[mx]])++l;
			while(deg[id[l]]>=deg[id[mx]])++r;
			F(i,0,n)tg[i]=false;
			F(i,0,l)tg[id[i]]=true;
			F(i,l,r)
			{
				int u=id[i],cnt=0;
				for(int v:adj[u])cnt+=tg[v];
				if(cnt!=l)
				{
					ok[u]=false;
					continue;
				}
				sum[u]=w[u];
				for(int v:adj[u])sum[u]^=v;
				ok[u]=true;
			}
			sort(id+l,id+r,[](int u,int v){return ok[u]!=ok[v]?ok[u]:sum[u]<sum[v];});
			siz-=l;
			while(r>l&&!ok[id[r-1]])--r;
			F(i,l,r-siz+1)
			{
				if(sum[i]==sum[i+siz-1])
				{
					mx=siz+l;
					F(j,0,siz)id[j+l]=id[j+i];
					break;
				}
			}
		}
		F(i,0,n)in[i]=false;
		F(i,0,mx)in[id[i]]=true;
		int ans1=1,ans2=1;
		F(i,0,n)if(!in[i])
		{
			int cnt=0;
			for(int j:adj[i])if(in[j])++cnt;
			if(cnt==mx-1)++ans1;
		}
		F(i,0,n)if(in[i]&&deg[i]==mx-1)ans2=0;
		if(!ans2){F(i,0,n)if(in[i]&&deg[i]==mx-1)++ans2;}
		else F(i,0,n)if(in[i]&&deg[i]==mx)++ans2;
		F(i,0,n)adj[i].clear();
		printf("%d %d\n",ans1,ans2);
	}
	return 0;
}