#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;

		vector<int> a(n);
		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;
			a[u - 1]++;
			a[v - 1]++;
		}
		sort(a.rbegin(), a.rend());
		
		if (n == 1) {
			cout << 1 << ' ' << 1 << '\n';
			continue;
		}
		for (int t = 0; t < 2; t++) {
			for (int k = 1; k < n; k++) {
				if (a[k - 1] >= k - 1 && a[k] <= k) {
					int x = a[k - 1];
					int y = a[k];
					int z = (k == n - 1) ? 0 : a[k + 1];

					if (y <= k - 1) {
						int p = k;
						while (p < n && a[p] == k - 1) ++p;

						cout << p - k + 1 << ' ';
					}
					else {
						int p = k;
						while (p < n && a[p] == k) ++p;

						cout << p - k << ' ';
					}
					break;
				}
			}
			for (int i = 0; i < n; i++) a[i] = n - 1 - a[i];
			reverse(a.begin(), a.end());
		}
		cout << '\n';
	}
}