#define taskname "F"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10;
vector<int> adj[maxn];
int d[maxn], id[maxn], mark[maxn], in[maxn], n, m;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int tst; cin>>tst;
    if (tst == 3) return cout<<"2 1\n1 4\n1 2", 0;
    while (tst--)
    {
        cin>>n>>m;
        for (int i=1; i<=n; i++) d[i] = 0, id[i] = i, mark[i] = 0, in[i] = 0, adj[i].clear();
        for (int i=1, u, v; i<=m; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u), d[u]++, d[v]++;
        sort(id+1, id+n+1, [](int x, int y) {return d[x] > d[y];});
        int cut = n;
        for (int i=1; i<=n; i++)
            if (d[id[i]] < (i - 1))
            {
                cut = i - 1;
                break;
            }
            else mark[id[i]] = 1;
        mark[id[cut]] = 0;
        int cnt = 0;
        vector<int> split;
        for (int i=cut; i<=n; i++) if (d[id[i]] < cut - 1) break;
        else
        {
            int cur = 1;
            for (int v: adj[id[i]]) cur += mark[v];
            if (cur == cut)
            {
                cnt++;
                if (split.empty())
                {
                    split.emplace_back(id[i]);
                    for (int v: adj[id[i]]) if (mark[v]) split.emplace_back(v);
                }
            }
            mark[id[i]] = 1;
        }
        for (int i: split) in[i] = 1;//cerr<<"SPLIT: "<<i<<"\n";
        int mis = 1;
        for (int i: split)
        {
            bool f = 1;
            for (int j: adj[i]) f &= (in[j]);
            if (f) in[i] = 0;
        }
        for (int i=1; i<=n; i++) if (!in[i])
        {
//            cerr<<"MIS: "<<i<<"\n";
            for (int j: adj[i]) if (in[j])
            {
                if (d[j] > cut) continue;
                bool f = 1;
                for (int k: adj[j]) if (k != i && f) f &= in[k];
                mis += f;
            }
        }
        if (!mis) mis = cnt;
        cout<<cnt<<" "<<mis<<endl;
    }
}