#include<bits/stdc++.h>
using ll = long long;
#define all(x) begin(x), end(x)
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n);
        for(int u, v, i = 0; i < m; i++) {
            cin >> u >> v;
            // cout << u << " " << v << " " << n << endl;
            g[--u].push_back(--v);
            g[v].push_back(u);
        }
        // n = 1e5;
        // m = 440 * 439 / 2;
        // for(int u = 0; u < n && m; u++) {
        //     for(int v = 0; v < u && m; v++) {
        //         g[u].push_back(v);
        //         g[v].push_back(u);
        //         m--;
        //     }
        // }
        {
            vector<int> in_clique(n), deg(n), mark(n);
            vector<int> cand(n); iota(all(cand), 0);
            for(int i = 0; i < n; i++) deg[i] = g[i].size();
            int size = 0;
            while(true) {
                pair<int, int> v = {-1, -1};
                for(auto i : cand) if(!in_clique[i]) {
                    v = max(v, {deg[i], i});
                }
                // for(auto i : cand) cout << i << ", "; cout << endl;
                if(v.first == -1) break;
                // cout << v.second <<"add"<< endl;
                size++;
                in_clique[v.second] = 1;
                for(auto i : g[v.second])
                    mark[i]++;
                vector<int> nc;
                for(auto i : cand) {
                    if((in_clique[i] == 0) & (mark[i] < size)) {//bad vertex
                        in_clique[i] = -1;
                        // for(auto &j : g[i])
                            // deg[j] -= in_clique[j] == 0;//kill vertex
                    }
                    if(in_clique[i] == 0) {
                        nc.push_back(i);
                    }
                }
                cand = nc;
            }
            int ans = 1, anti_ans = 1;
            for(int i = 0; i < n; i++) if(in_clique[i] <= 0) {
                int d = 0;
                for(auto j : g[i]) d += in_clique[j] == 1;
                ans += d + 1 == size;
                // cout << i << " " << d << endl;
            }
            cout << ans << " ";
        }
        
        {
            vector<int> in_clique(n), deg(n), mark(n);
            set<pair<int, int>, greater<>> best;
            for(int i = 0; i < n; i++) {
                deg[i] = n - 1 - g[i].size();
                best.insert({deg[i], i});
            }
            int size = 0;
            while(!best.empty()) {
                pair<int, int> v = *best.begin();
                size++;
                in_clique[v.second] = 1;
                best.erase(best.begin());
                for(auto i : g[v.second]) {
                    if(in_clique[i] == 0) {
                        in_clique[i] = -1;
                        best.erase({deg[i], i});
                        // for(auto j : g[i]) if(best.count({deg[j], j})) {
                        //     best.erase({deg[j], j});
                        //     deg[j]++;
                        //     best.insert({deg[j], j});
                        // }
                    }
                }
            }
            int ans = 1;
            for(int i = 0; i < n; i++) if(in_clique[i] <= 0) {
                int d = 0;
                for(auto j : g[i]) d += in_clique[j] == 1;
                ans += d == 1;
            }
            cout << ans << "\n";
        }
    }
}