#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,d[N],ans1,ans2,t;
int a[N];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);ans1=ans2=0;
        for(int i=1;i<=n;++i) d[i]=0,a[i]=i;
        for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),++d[u],++d[v];
        sort(a+1,a+n+1,[&](int A,int B){return d[A]>d[B];});
        for(int i=n;i;--i)
            if(d[a[i]]>=i-1){
                t=i;
                break;
            }
        // printf("t=%d\n",t);
        // for(int i=1;i<=n;++i) printf("%d ",d[a[i]]);puts("");
        ans1=1;
        for(int i=t+1;i<=n;++i) if(d[a[i]]>=t-1) ++ans1;
        for(int i=1;i<=t;++i) if(d[a[i]]==t-1) ans2++;
        if(!ans2){
            ans2=1;
            if(d[a[t]]==t) 
                for(int i=1;i<=n;++i) if(d[a[i]]==t) ++ans2;
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}