#include<bits/stdc++.h>
using namespace std;

const int N=1e5+1e3+7;

int T,n,m;

vector<int> g[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			g[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			g[u].push_back(v);
			g[v].push_back(u);
		}
		set<int>c,e;
		vector<int>id;
		for(int i=1;i<=n;i++)
			id.push_back(i);
		sort(id.begin(),id.end(),[&](const int &a,const int &b) {
			return g[a].size()>g[b].size();
		});
		for(auto x:id)
		{
			int t=0;
			for(auto v:g[x])
				if(c.count(v))
					t++;
			if(t==c.size())
				c.insert(x);
			else
				break;
		}
		for(int i=1;i<=n;i++)
			if(!c.count(i))
				e.insert(i);
		int ans=1;
		for(auto x:e)
		{
			int t=0;
			for(auto v:g[x])
				if(c.count(v))
					t++;
			if(t==(int)c.size()-1)
				ans++;
		}
		printf("%d ",ans);
		map<int,int>cs;
		for(auto x:c)
		{
			int t=0;
			for(auto v:g[x])
				if(e.count(v))
					t++;
			cs[t]++;
		}
		if(cs[0])
			ans=cs[0];
		else
			ans=cs[1]+1;
		printf("%d\n",ans);
	}
}