#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 100010;

vector <int> e[N];
int du[N], vis[N], a[N];
// P ksj[N];
bool cmp(int a, int b) {
    return du[a] > du[b];
}
int main() {
    int T; 
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        rep (i, 1, m) {
            int u, v;
            scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
            du[u]++;
            du[v]++;
        }
        rep (i, 1, n) a[i] = i;
        sort(a+1, a+n+1, cmp);
        int num = 0;
        rep (i, 1, n) {
            int cnt = 0;
            int u = a[i];
            for (int j = 0; j < du[u]; j++) {
                int v = e[u][j];
                cnt += vis[v];
            }
            if (cnt == num) {
                vis[u] = 1;
                num++;
            }
        }

        int ans1 = 0;
        rep (i, 1, n) {
            if (du[i] >= num - 1) ans1++;
        }
        cout << ans1 - num + 1<< ' ';

        int ans2 =0, flag = 0;
        rep (i, 1, n) {
            if (du[i] == num-1 && vis[i]) flag = 1;
        }
        if (flag == 1) {
            rep (i, 1, n) {
                if (du[i] == num-1 && vis[i]) ans2++;
            }
        } else {
            ans2++;
            rep (i, 1, n) {
                if (du[i] == num && vis[i]) ans2++;
            }
        }
        cout << ans2;
        cout <<'\n';
        rep (i, 1, n) {
            du[i] = 0;
            e[i].clear();
            vis[i] = 0;
        }
    }

    return 0;
}