#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5, M = 2e7 + 7;
int T, n, m, u, v, edgenum, Head[N], Next[M], vet[M], nodes, cnt, TIME, id[N], top, stk[N], instk[N], low[N], dfn[N], t[N], s[2][N], c[2], bid[N];
basic_string <int> adj[100005];
void add(int u, int v) {
	Next[++edgenum] = Head[u];
	Head[u] = edgenum;
	vet[edgenum] = v;
}
void build(int p, int l, int r) {
	if (l == r) return void (id[p] = l);
	int mid = l + r >> 1;
	id[p] = ++ nodes;
	build(p<<1, l, mid), add(id[p], id[p<<1]);
	build(p<<1|1, mid+1, r), add(id[p], id[p<<1|1]);
}
void update(int p, int l, int r, int x, int y, int z) {
	if (l == x && r == y) return add(z, id[p]);
	int mid = l + r >> 1;
	if (y <= mid) update(p<<1, l, mid, x, y, z);
	else if (x > mid) update(p<<1|1, mid+1, r, x, y, z);
	else update(p<<1, l, mid, x, mid, z), update(p<<1|1, mid+1, r, mid+1, y, z);
}
void Tarjan(int u, int fa) {
	low[u] = dfn[u] = ++ TIME, stk[++top] = u, instk[u] = 1;
	for (int e=Head[u]; e; e=Next[e]) {
		int v=vet[e];
		if (! dfn[v]) Tarjan(v, u), low[u] = min(low[u], low[v]);
		else if (instk[v]) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		cnt ++;
		do bid[stk[top]] = cnt, instk[stk[top]] = 0;
		while (stk[top--] ^ u);
	}
}
int main() {
	cin >> T;
	while (T --) {
		scanf ("%d%d", &n, &m);
		if (! m) { printf ("%d %d\n", n, 1); continue; }
		if (m == n * (n - 1) >> 1) { for (int i=1; i<=m; i++) scanf ("%*d%*d"); printf ("%d %d\n", 1, n); continue; }
		for (int i=1; i<=n; i++)
			adj[i]. clear(), adj[i] += i; edgenum = 0;
		for (int i=1; i<=m; i++) {
			scanf ("%d%d", &u, &v), adj[u] += v, adj[v] += u;
			add(u, n + v), add(v, n + u);
		} nodes = n << 1;
		build(1, 1, n);
		for (int i=1; i<=n; i++) {
			int l = 0;
			sort (adj[i]. begin(), adj[i]. end());
			for (int j : adj[i]) {
				if (l + 1 < j) update(1, 1, n, l + 1, j - 1, n + i); //, cerr << n + i << ' ' << l + 1 << ',' << j - 1 << endl;
				l = j;
			}
			if (l < n) update(1, 1, n, l + 1, n, n + i); //, cerr << n + i << ' ' << l + 1 << ',' << n << endl;
		} cnt = TIME = 0;
		for (int i=1; i<=nodes; i++)
			dfn[i] = 0;
		for (int i=1; i<=nodes; i++)
			if (! dfn[i]) Tarjan(i, 0);
		c[0] = c[1] = 0;
		for (int i=1; i<=n; i++)
			t[i] = bid[i] > bid[n+i], s[t[i]][++c[t[i]]] = i; //, cerr << t[i]; cerr << endl;
		int mx = - 1, mc;
		for (int i=1; i<=c[0]; i++) {
			int now = 0;
			for (int j : adj[s[0][i]]) now += t[j];
			if (now > mx) mx = now, mc = 0;
			if (now == mx) mc ++;
		}
		printf ("%d ", mx == c[1] ? mc : mx == c[1] - 1 ? mc + 1 : 1);
		mx = - 1;
		for (int i=1; i<=c[1]; i++) {
			int now = c[0];
			for (int j : adj[s[1][i]]) now -= ! t[j];
			if (now > mx) mx = now, mc = 0;
			if (now == mx) mc ++;
		}
		printf ("%d\n", mx == c[0] ? mc : mx == c[0] - 1 ? mc + 1 : 1);
		for (int i=1; i<=nodes; i++)
			Head[i] = 0;
	}
}