#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i, a, b) for(int i = a; i <= b; i ++)
#define REP(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define fr first
#define sd second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define N 100010
int n, m;
int deg[N], num[N], s[N];
int calc()
{
	REP(i, n, 0)s[i] = s[i + 1] + num[i];
	REP(M, n, 1)
	{
		if(s[M] <= M && s[M - 1] >= M)
		{
			return s[M - 1] - M + 1;
		}
	}
	exit(-1);
}
void sol()
{
	n = read(), m = read();
	FOR(i, 1, m)
	{
		int x = read(), y = read();
		deg[x] ++, deg[y] ++;
	}
	FOR(i, 0, n)num[i] = 0;
	FOR(i, 1, n)num[deg[i]] ++;
	cout << calc() << ' ';
	FOR(i, 1, n)deg[i] = n - 1 - deg[i];
	FOR(i, 0, n)num[i] = 0;
	FOR(i, 1, n)num[deg[i]] ++;
	cout << calc() << '\n';
	FOR(i, 0, n + 1)deg[i] = s[i] = num[i] = 0;
}
int main()
{
	int T = read();
	while(T --)sol();
	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
*/
/*
1
6 6
1 2
2 3
1 3
1 4
2 5
3 6
*/