#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[100000], *p1, *p2;
inline int read() {
	char ch; int x = 0; while ((ch = gc) < 48); do x = x * 10 + ch - 48; while ((ch = gc) >= 48); return x;
}
int deg[100005], a[100005], bel[100005], seq[100005], n, m;
bool vis[100005];
std::vector<int> G[100005], vec[100005];
int adjust1() {
	int cnt = 0;
	for (int i = 1; i <= n; ++ i) if (bel[i]) ++ cnt;
	for (int i = 1; i <= n; ++ i) if (!bel[i]) {
		int x = 0;
		for (int j : G[i]) if (bel[j]) ++ x;
		if (x == cnt) return i;
	}
	return 0;
}
int adjust2() {
	for (int i = 1; i <= n; ++ i) if (bel[i]) {
		bool flag = true;
		for (int j : G[i]) if (!bel[j]) {flag = false; break;}
		if (flag) return i;
	}
	return 0;
}
int calc1() {
	memset(vis, false, sizeof vis);
	int cnt = 0, ans = 1;
	for (int i = 1; i <= n; ++ i) if (bel[i]) seq[++ cnt] = i;
	for (int i = 1; i <= n; ++ i) if (!bel[i] && deg[i] >= cnt - 1) {
		int tot = 0;
		for (int j : G[i]) vis[j] = true, tot += bel[j];
		if (tot == cnt - 1) {
			int v = 0;
			for (int j = 1; j <= cnt; ++ j) if (!vis[seq[j]]) {v = seq[j]; break;}
			if (deg[v] == cnt - 1) ++ ans;
		}
		for (int j : G[i]) vis[j] = false;
	}
	return ans;
}
int calc2() {
	memset(vis, false, sizeof vis);
	int cnt = 0, ans = 1;
	for (int i = 1; i <= n; ++ i) if (bel[i]) ++ cnt;
	for (int i = 1; i <= n; ++ i) if (bel[i] && deg[i] == cnt) ++ ans;
	return ans;
}
bool check() {
	for (int u = 1; u <= n; ++ u)
	for (int v : G[u]) assert(bel[u] || bel[v]);
	int cnt = 0;
	for (int i = 1; i <= n; ++ i) if (bel[i]) seq[++ cnt] = i;
	for (int u = 1; u <= cnt; ++ u) {
		int jb=0;
		for (int v : G[seq[u]]) jb += bel[v];
		assert(jb == cnt - 1);
	}
	return true;
}

int main() {
	int _ = read();
	while (_ --) {
		memset(deg, 0, sizeof deg);
		n = read(), m = read();
		for (int i = 0; i <= n; ++ i) vec[i].clear(), G[i].clear(), deg[i] = bel[i] = 0;
		for (int i = 1, u, v; i <= m; ++ i) {
			u = read(), v = read();
			if (u > v) u ^= v ^= u ^= v;
			G[u].emplace_back(v), G[v].emplace_back(u), ++ deg[u], ++ deg[v];
		}
		if (!m) {printf("%d 1\n", n); continue;}
		if (m == 1ll * n * (n - 1) >> 1) {printf("1 %d\n", n); continue;}
		for (int i = 1; i <= n; ++ i) vec[deg[i]].emplace_back(i);
		for (int i = 0, k = 0; i <= n; ++ i) for (int j : vec[i]) a[++ k] = j;
		int l = n - 1;
		memset(vis, false, sizeof vis);
		for (int i = 1; i <= n; ++ i) {
			for (int j : G[a[i]]) if (vis[j]) {l = i - 1; break;}
			if (l != n - 1) break;
			vis[a[i]] = true;
		}
		for (int i = l + 1; i <= n; ++ i) bel[a[i]] = 1;
		int t = adjust1(); bel[t] = 1; check();printf("%d ", calc1());
		bel[t] = 0; bel[adjust2()] = 0; check();printf("%d\n", calc2());
	}
	return 0;
}