#include<cstdio>
#include<map> 
#include<algorithm>
#include<cstring>
#pragma GCC optimize(3)
using namespace std;

int read_int(){
	char c;
	while(((c = getchar()) < '0' || c > '9') && c != '-');
	bool flag = false;
	int x = 0;
	if(c == '-'){
		flag = true;
	}
	else{
		x = c - '0';
	}
	while((c = getchar()) >= '0' && c <= '9'){
		x = x * 10 + c - '0';
	}
	if(flag)
		return -x;
	return x;
}


struct Edge{
	int v,next;
}Map[200500];
int Head[100500];
struct Node{
	long long v;
	int i;
}Degree[100500];

void addedge(int num,int from,int go){
	Map[num].v = go;
	Map[num].next = Head[from];
	Head[from] = num;
	Degree[from].v += 1;
}

int cmp(Node a,Node b)
{
	return a.v>b.v;
}

int solve1(int n,int m,int flag)
{
	int i=0;
	map<int,int> Mp;
	int Ans = 0;
	for(i=1;i<=n;i++){
		if(Degree[i].v == Ans-1)
			break;
		Ans+=1;
	}
	for(int j = i;j <= n;j++){
		if(Degree[j].v == Ans)
			continue;
		Mp[Degree[j].i] = 1;
	}
	int Final_Ans = 1;
	while(Degree[i].v==Ans-1){
		int check = 0;
		for(int j = Head[Degree[i].i];j!=0;j = Map[j].next){
			if(Mp[Map[j].v] == 1){
				check = 1;
				break;
			}
		}
		if(check == 0){
			Final_Ans += 1;
		}
		i+=1;
	}
	return Final_Ans;
}

int solve2(int n,int m)
{
	int i=0;
	map<int,int> Mp;
	int Ans = 0;
	
	for(int i=1;i<=n;i++){
		Degree[i].v = n-1-Degree[i].v;
	}
	
	for(i=n;i>=1;i--){
		if(Degree[i].v == Ans-1)
			break;
		Ans+=1;
	}
	for(int j = i;j <= n;j++){
		if(Degree[j].v == Ans-1)
			continue;
		Mp[Degree[j].i] = 1;
	}
	int Final_Ans = 1;
	while(Degree[i].v==Ans-1){
		int check = 0;
		for(int j = Head[Degree[i].i];j!=0;j = Map[j].next){
			if(Mp[Map[j].v] == 0){
				check += 1;
				break;
			}
		}
		if(check == 1){
			Final_Ans += 1;
		}
		i-=1;
	}
	return Final_Ans;
}


int main()
{
	int T;
	scanf("%d",&T);
	int flag = 0;
	while(T--)
	{
		flag += 1;
		int n,m;
		scanf("%d%d",&n,&m); 
//		n = read_int();
//		m = read_int();
		if(m == 0){
			printf("%d %d\n",n,1);
			continue;
		}
		for(int i=0;i<=n+5;i++){
			Degree[i].v = 0;
			Degree[i].i = i;
			Head[i] = 0;
		}
		int i=0;
		for(int j=1;j<=m;j++){
			int a,b;
			scanf("%d%d",&a,&b);
			//a = read_int();
			//b = read_int();
			addedge(++i,a,b);
			addedge(++i,b,a);
		}
		sort(Degree+1,Degree+n+1,cmp);
		int Ans1 = solve1(n,m,flag);
		int Ans2 = solve2(n,m);
		printf("%d %d\n",Ans1,Ans2);
	}
	return 0;
}
/*
3
3 2
1 2
2 3
6 6
1 2
2 3
1 3
1 4
2 5
3 6
4 1
1 2

12 11
6 2 
6 5 
6 7 
6 8 
6 11 
6 9 
6 3 
6 10 
6 4 
6 1 
6 12

1
15 40
13 14
11 13
8 15
13 3
13 6
10 5
8 11
14 1
15 3
8 14
11 3
11 15
8 12
10 1
8 1
1 6
13 15
11 1
5 15
10 3
10 11
15 1
8 5
15 14
10 15
8 3
13 4
5 1
5 13
10 13
11 14
10 8
14 6
8 13
10 14
13 1
5 14
1 12
11 6
11 5 

*/