#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int deg[100007], p[100007];
bool mark[100007];

inline void init(int n){
	for (int i = 1; i <= n; i++){
		deg[i] = 0;
	}
}

inline int read(){
	int ans = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9'){
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans;
}

void write(int n){
	if (n >= 10) write(n / 10);
	putchar(n % 10 + '0');
}

bool cmp(const int a, const int b){
	return deg[a] > deg[b];
}

int main(){
	int t = read();
	for (int i = 1; i <= t; i++){
		int n = read(), m = read();
		if (m == 0){
			write(n);
			putchar(' ');
			putchar('1');
			putchar('\n');
			continue;
		}
		int cnt = 1, ans1 = 1, ans2 = 0;
		init(n);
		for (int j = 1; j <= m; j++){
			int a = read(), b = read();
			deg[a]++;
			deg[b]++;
		}
		for (int j = 1; j <= n; j++){
			p[j] = j;
		}
		sort(p + 1, p + n + 1, cmp);
		while (cnt < n && !(deg[p[cnt]] >= cnt - 1 && deg[p[cnt + 1]] <= cnt - 1)) cnt++;
		for (int j = cnt + 1; j <= n && deg[p[j]] == cnt - 1; j++){
			ans1++;
		}
		for (int j = cnt; j >= 1 && deg[p[j]] == cnt - 1; j--){
			ans2++;
		}
		if (ans2 == 0){
			ans2 = 1;
			for (int j = cnt; j >= 1 && deg[p[j]] == cnt; j--){
				ans2++;
			}
		}
		write(ans1);
		putchar(' ');
		write(ans2);
		putchar('\n');
	}
	return 0;
}