#include <stdio.h>

#include <vector>

using namespace std;

typedef struct {
	int nxt;
	int end;
} Edge;

int cnt;
int head[100007], deg[100007], root[100007], sz[100007];
bool mark[100007], mark2[100007];
Edge edge[200007];

inline void init(int n){
	cnt = 0;
	for (int i = 1; i <= n; i++){
		head[i] = deg[i] = 0;
		root[i] = i;
		sz[i] = 1;
		mark[i] = mark2[i] = false;
	}
}

inline void add_edge(int start, int end){
	cnt++;
	edge[cnt].nxt = head[start];
	head[start] = cnt;
	edge[cnt].end = end;
}

int get_root(int x){
	if (root[x] == x) return x;
	return root[x] = get_root(root[x]);
}

inline void merge(int x, int y){
	int x_root = get_root(x), y_root = get_root(y);
	if (x_root != y_root){
		root[x_root] = y_root;
		sz[y_root] += sz[x_root];
	}
}

inline void update(int p, int q, int &x, int &y){
	if (x < p){
		x = p;
		y = q;
	} else if (x == p){
		y += q;
	}
}

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++){
		int n, m;
		scanf("%d %d", &n, &m);
		if (m == 0){
			printf("%d 1\n", n);
			continue;
		}
		int ncon = 0;
		init(n);
		for (int j = 1; j <= m; j++){
			int a, b;
			scanf("%d %d", &a, &b);
			deg[a]++;
			deg[b]++;
			add_edge(a, b);
			add_edge(b, a);
			merge(a, b);
		}
		vector<int> tuan, must, candiate;
		for (int j = 1; j <= n; j++){
			int csz = sz[get_root(j)];
			if (csz == 1){
				ncon++;
			} else {
				tuan.push_back(j);
			}
		}
		int mxv = 0, cnt;
		while (1ll * mxv * (mxv + 1) / 2 <= m) mxv++;
		for (int j = mxv; j >= 2; j--){
			vector<int> _must, _candiate;
			for (int k : tuan){
				mark[k] = false;
			}
			for (int k : tuan){
				if (deg[k] == j - 1){
					for (int l = head[k]; l != 0; l = edge[l].nxt){
						mark[edge[l].end] = true;
					}
				} else if (deg[k] >= j){
					mark[k] = true;
				}
			}
			for (int k : tuan){
				if (deg[k] >= j - 1){
					if (mark[k]){
						_must.push_back(k);
					} else {
						_candiate.push_back(k);
					}
				}
			}
			if (_candiate.size() == 1){
				_must.push_back(_candiate[0]);
				_candiate.pop_back();
			}
			if (_must.size() > j || _must.size() + _candiate.size() < j) continue;
			cnt = j;
			must = _must;
			candiate = _candiate;
			break;
		}
		int cnt1 = -1, ans1, cnt2 = -1, ans2;
		for (int j : tuan){
			mark[j] = mark2[j] = false;
		}
		if (must.size() == cnt){
			for (int j : must){
				mark[j] = true;
			}
			update(cnt, 1, cnt1, ans1);
			for (int k : must){
				for (int l = head[k]; l != 0; l = edge[l].nxt){
					if (!mark[edge[l].end]) update(2, 1, cnt1, ans1);
				}
			}
			update(n - cnt, 1, cnt2, ans2);
			for (int k : must){
				int tot = n - cnt + 1;
				for (int l = head[k]; l != 0; l = edge[l].nxt){
					if (!mark[edge[l].end]) tot--;
				}
				update(tot, 1, cnt2, ans2);
			}
		} else {
			for (int j : must){
				mark[j] = true;
			}
			for (int j : candiate){
				mark2[j] = true;
			}
			update(cnt, candiate.size(), cnt1, ans1);
			for (int k : must){
				for (int l = head[k]; l != 0; l = edge[l].nxt){
					int x = edge[l].end;
					if (!mark[x] && !mark2[x]) update(2, 1, cnt1, ans1);
				}
			}
			update(n - must.size(), 1, cnt2, ans2);
			for (int k : must){
				int tot = n - cnt + 1;
				for (int l = head[k]; l != 0; l = edge[l].nxt){
					if (!mark[edge[l].end]) tot--;
				}
				update(tot, 1, cnt2, ans2);
			}
		}
		printf("%d %d\n", ans1, ans2);
	}
	return 0;
}