#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "../../debug.h"
#else
#define dbg(...) 787788
#endif

void solve() {
    int tc;
    cin >> tc;
    for (int t = 0; t < tc; t++) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int fr, to;
            cin >> fr >> to;
            fr -= 1;
            to -= 1;
            g[fr].push_back(to);
            g[to].push_back(fr);
        }
        vector<int> perm;
        for (int i = 0; i < n; i++) {
            perm.push_back(i);
        }
        sort(perm.begin(), perm.end(), [&](int a, int b) {
            return g[a].size() < g[b].size();
        });
        vector<bool> in_cliq(n, false);
        int cliq = 0;
        for (int pos = n - 1; pos >= 0; pos--) {
            int v = perm[pos];
            int cnt = 0;
            for (int to : g[v]) {
                if (in_cliq[to]) {
                    cnt++;
                }
            }
            if (cnt == cliq) {
                in_cliq[v] = true;
                cliq++;
            } else {
                break;
            }
        }
        for (int v = 0; v < n; v++) {
            if (!in_cliq[v]) {
                for (int to : g[v]) {
                    assert(in_cliq[to]);
                }
            }
        }
        int full_cliq = 0;
        int almost_cliq = 0;
        for (int v = 0; v < n; v++) {
            if (!in_cliq[v]) {
                int cnt_in_cliq = 0;
                for (int to : g[v]) {
                    if (in_cliq[to]) {
                        cnt_in_cliq++;
                    }
                }
                if (cnt_in_cliq == cliq) {
                    full_cliq += 1;
                } else {
                    if (cnt_in_cliq == cliq - 1) {
                        almost_cliq += 1;
                    }
                }
            }
        }
        int cliq_res = full_cliq == 0 ? (almost_cliq + 1) : full_cliq;

        int full_not_cliq = 0;
        int almost_not_cliq = 0;
        for (int v = 0; v < n; v++) {
            if (in_cliq[v]) {
                int cnt_not_in_cliq = 0;
                for (int to : g[v]) {
                    if (!in_cliq[to]) {
                        cnt_not_in_cliq++;
                    }
                }
                if (cnt_not_in_cliq == 0) {
                    full_not_cliq += 1;
                } else if (cnt_not_in_cliq == 1) {
                    almost_not_cliq += 1;
                }
            }
        }
        int not_cliq_res = full_not_cliq == 0 ? (almost_not_cliq + 1) : full_not_cliq;
        cout << cliq_res << " " << not_cliq_res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

#ifdef LOCAL
#include <filesystem>
    run_all_tests(solve);
    // run_single_test(solve, 1);
    // solve();
#else
    solve();
#endif
}