#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<int> adj[N];

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		adj[i].clear();
	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int i, int j) {
		return sz(adj[i]) < sz(adj[j]);
	});
	for (int i = 0; i < n; i++) {
		sort(adj[i].begin(), adj[i].end(), [&](int u, int v) {
			return idx[u] > idx[v];
		});
	}

	auto is_conn = [&](int u, int v) {
		auto it = lower_bound(all(adj[u]), v, [&](int i, int j) {
			return idx[i] > idx[j];
		});
		if (it != adj[u].end() && *it == v)
			return 1;
		return 0;
	};

	vector<int> cl, vis(n);
	for (int i = n - 1; i >= 0; i--) {
		int o = 1;
		for (int j: cl) {
			o &= is_conn(idx[i], j);
			if (o == 0)
				break;
		}
		if (o == 0) {
			int x = 1, y = 1;
			for (int j = i; j >= 0; j--)
				x += sz(adj[idx[j]]) == sz(cl) - 1;
			if (sz(adj[idx[i+1]]) == sz(cl) - 1)
				i++, cl.pop_back();
			for (int j: cl)
				y += sz(adj[j]) <= sz(cl);
			cout << x << " " << y << "\n";
			return;
		}
		vis[idx[i]] = 1;
		cl.push_back(idx[i]);
	}
	cout << 1 << " " << n << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t; cin >> t; while (t--) solve();
}