#include<bits/stdc++.h>
using namespace std;
int T,n,m,u,v,s,ans1,ans2;
vector<int> edge[105000];
typedef pair<int,int> PII;
PII pii[105000];
int deg[105000];
int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++) {
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
            deg[u]++;deg[v]++;
        }
        for (int i=1;i<=n;i++) pii[i]={deg[i],i};
        sort(pii+1,pii+1+n);
        reverse(pii+1,pii+1+n);
        s=ans1=ans2=0;
        for (int i=1;i<=n;i++) {
            if (pii[i].first>=i-1) s++;
            else break;
        }
        ans1++;
        for (int i=s+1;i<=n;i++) {
            if (pii[i].first==s-1) ans1++;
        }
        if (pii[s].first<=s) {
            for (int i=s;i>=1;i--) {
                if (pii[i].first==pii[s].first) ans2++;
            }
        }
        if (pii[s].first>=s) ans2++;
        cout<<ans1<<' '<<ans2<<endl;
        for (int i=1;i<=n;i++) {
            pii[i]={0,0};
            deg[i]=0;
            edge[i].clear();
        }
    }
    return 0;
}