#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
mt19937 rnd(51569);
int n,m,limits,cnt0,cnt1,s0[maxn],s1[maxn];
int id[maxn],c[maxn],vis[maxn];
vector<int>to[maxn],O;
void dfs0(int x);
void dfs1(int x);
int flag;
void dfs0(int x) {
	c[x]=1;
	s0[++cnt0]=x;
//	gdb(x,c[x]);
	for (auto y:to[x]) {
		if (!c[y]) dfs1(y);
		else if (c[x]==c[y]) {flag=1;return ;}
		if (flag==1) return ;
	}
}
int tot;
void dfs1(int x) {
	++tot;c[x]=2;int i;
//	gdb(x,c[x]);
	s1[++cnt1]=x;
	if (tot>=limits) {flag=1;return ;}
	for (i=1;i<=n;i++) vis[i]=0;
	for (auto y:to[x]) vis[y]=1;vis[x]=1;
	for (i=1;i<=n&&!flag;i++) if (!vis[i]) {
//		gdb(x,i,c[x],c[i]);
		if (!c[i]) dfs0(i);
		else if (c[x]==c[i]) {flag=1;return ;}
	} 
}
void check(void) {
	
}
void calc(void) {
	int i,ans1=0,ans2=0,nums1=0,nums2=0,tmp=0;
//	for (i=1;i<=n;i++) gdb(i,c[i]);
	for (i=1;i<=n;i++) vis[i]=0,c[i]=max(c[i],1);
	for (i=1;i<=n;i++) 
		if (c[i]==1) flag&=((int)to[i].size()==0),nums1++;
		else vis[i]=1,nums2++;
	for (i=1;i<=n;i++) if (c[i]==1) {
		int tot=0;
		for (auto y:to[i]) if (vis[y]) tot++; 
		if (tot==nums2) nums2++,tmp=i,vis[i]=1,c[i]=2;
	}
	for (i=1;i<=n;i++) if (c[i]==1) {
		int tot=0;
		for (auto y:to[i]) if (vis[y]) tot++;
		if (tot==nums2-1) ans1++;
	}
	vis[tmp]=0,c[tmp]=1;
	
	for (i=1;i<=n;i++) if (c[i]!=1) {
		int tot=1;
		for (auto y:to[i]) if (vis[y]==0) tot=0;
		if (tot==1) nums1++;
	}
	for (i=1;i<=n;i++) if (c[i]!=1) {
		int tot=0;
		for (auto y:to[i]) if (vis[y]==0) tot++;
		if (tot==1) ans2++;
	}
//	gdb(nums1,nums2);
	printf("%d %d\n",ans1+1,ans2+1);
}
int in[maxn];
bool cmp(int x,int y) {return in[x]>in[y];}
void solve(void) {
	int i,j,x,y;
	read(n);read(m);limits=sqrt(m)*2+5;
	for (i=1;i<=n;i++) in[i]=0,to[i].clear(),c[i]=0;
	for (i=1;i<=m;i++) {
		read(x);read(y);
		in[x]++,in[y]++;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for (i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+1+n,cmp);
	for (i=1;i<=n;i++) {
		while (cnt0) c[s0[cnt0]]=0,cnt0--;
		while (cnt1) c[s1[cnt1]]=0,cnt1--;
		for (j=1;j<=n;j++) assert(c[j]==0);
		x=id[i];O.clear();
		flag=0;tot=0;dfs1(x);
//		gdb(id[i],flag);
		if (flag==0) {
			calc();
			return ;
		}
	}
//	gdb(n,m);
}
signed main(void){
//	freopen("1.in","r",stdin);
	int T;
	read(T);while (T--) solve();
	return 0;
}