// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int T, n, m, vis[100005];
struct graph {
	int tot, hd[100005];
	int nxt[200005], to[200005];

	void clear(int n) {tot = 0; memset(hd, 0, sizeof(int) * n); return;}
	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return;
	}
} g;
int l[100005], p[100005], pos[100005], q[100005];
vector<int> vec[100005];
int deg[100005], cnt[100005];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) vis[i] = deg[i] = cnt[i] = 0;
		g.clear(n + 5);
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			g.add(u, v), g.add(v, u);
			deg[u]++, deg[v]++;
		}
		for (int i = 1; i <= n; i++) l[i] = 0, pos[i] = vec[0].size(), vec[0].push_back(i);
		for (int i = 1, j = 0; i <= n; i++, j++) {
			while (vec[j].empty()) j--;
			int u = p[i] = vec[j].back();
			vec[j].pop_back();
			pos[u] = -1;
			for (int k = g.hd[u]; k; k = g.nxt[k])
				if (pos[g.to[k]] != -1) {
					int v = g.to[k];
					pos[vec[l[v]].back()] = pos[v];
					swap(vec[l[v]][pos[v]], vec[l[v]].back());
					vec[l[v]].pop_back();
					pos[v] = vec[++l[v]].size();
					vec[l[v]].push_back(v);
				}
		}
		reverse(p + 1, p + n + 1);
		for (int i = 1; i <= n; i++) q[p[i]] = i;
		int mx = 0, id = 0;
		for (int i = 1; i <= n; i++) {
			int num = 1;
			for (int j = g.hd[p[i]]; j; j = g.nxt[j]) num += q[g.to[j]] > i;
			if (num > mx) mx = num, id = p[i];
		}
		int ans1 = 1, ans2 = 1;
		vis[id] = 1;
		for (int i = g.hd[id]; i; i = g.nxt[i])
			if (q[g.to[i]] > q[id]) vis[g.to[i]] = 1;
		for (int i = 1; i <= n; i++)
			if (!vis[i]) {
				ans1 += deg[i] == mx - 1;
				for (int j = g.hd[i]; j; j = g.nxt[j])
					if (vis[g.to[j]]) cnt[g.to[j]]++;
			}
		for (int i = 1; i <= n; i++) ans2 += cnt[i] == 1;
		for (int i = 1; i <= n; i++)
			if (vis[i] && !cnt[i]) {
				ans2 = 0;
				for (int i = 1; i <= n; i++) ans2 += vis[i] && !cnt[i];
				break;
			}
		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
*/