#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<ll,ll> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=1e5+10;

vector<int>vect[maxn];
int deg[maxn],cnt[maxn],cnt2[maxn];
int n,m;

bool srt(int a,int b){
    return deg[a]<deg[b] || (deg[a]==deg[b] && cnt[a]<cnt[b]);
}

void rerun(int &css,vector<pii>cand,vector<int>a){

    css=1;
    for(int i=1;i<=n;i++){
        deg[i]=n-1-deg[i];
        cnt[i]=0;
        cnt2[i]=0;
    }
    reverse(a.begin(),a.end());
    cand.clear();
    cand.pb({0,0});
    for(int i=1;i<n;i++){
        if(deg[a[i]]==deg[a[i-1]]){
            cand[cand.size()-1].ss++;
        }
        else cand.pb({i,i});
    }

    for(int i=1;i<=n;i++){
        sort(vect[i].begin(),vect[i].end(),srt);
        for(int j=0;j<vect[i].size();j++){
            if(deg[i]<=deg[vect[i][j]]){
                cnt[i]--;
            }
            if(deg[i]<deg[vect[i][j]]){
                cnt2[i]--;
            }
        }
    }

    int c=0;
    for(int i=cand.size()-1;i>=0;i--){

        int l=cand[i].ff;
        int r=cand[i].ss;

        for(int j=l;j<=r;j++){
            cnt[a[j]]+=c+r-l;
            cnt2[a[j]]+=c;
        }

        int e=1;
        for(int j=l;j<=r;j++)
            if(cnt[a[j]]<c+r-l)e=0;


        if(e){
            c+=r-l+1;
            continue;
        }
        if( deg[a[r]]<c ){
            css=1;
            if(deg[a[r]]!=c-1)break;
            for(int j=l;j<=r;j++){
                if(cnt2[a[j]]==c-1)css++;
            }
        }
        else css=c+r-l+1-deg[a[r]];
        break;


    }


}

int main() {


   /// freopen("test2.txt","r",stdin);

    int q;
    scanf("%d",&q);
    while(q--){

        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++){
            deg[i]=0;
            vect[i].clear();
            cnt[i]=0;
            cnt2[i]=0;
        }
        for(int i=1;i<=m;i++){

            int u,v;
            scanf("%d %d",&u,&v);
            vect[u].pb(v);
            vect[v].pb(u);

            deg[u]++;
            deg[v]++;

        }


        for(int i=1;i<=n;i++){
            sort(vect[i].begin(),vect[i].end(),srt);

            for(int j=0;j<vect[i].size();j++){
                if(deg[i]<=deg[vect[i][j]]){
                    cnt[i]++;
                }
                if(deg[i]<deg[vect[i][j]]){
                    cnt2[i]++;
                }
            }

        }

        vector<int>a(n);
        for(int i=1;i<=n;i++)
            a[i-1]=i;
        sort(a.begin(),a.end(),srt);

        vector<pii>cand;
        cand.pb({0,0});
        for(int i=1;i<n;i++){
            if(deg[a[i]]==deg[a[i-1]]){
                cand[cand.size()-1].ss++;
            }
            else cand.pb({i,i});
        }

        int c=0;
        int css=1;
        for(int i=cand.size()-1;i>=0;i--){

            int l=cand[i].ff;
            int r=cand[i].ss;

            int e=1;
            for(int j=l;j<=r;j++)
                if(cnt[a[j]]<c+r-l)e=0;


            if(e){
                c+=r-l+1;
                continue;
            }

            if( deg[a[r]]<c ){
                css=1;
                if(deg[a[r]]!=c-1)break;
                for(int j=l;j<=r;j++){
                    if(cnt2[a[j]]==c-1)css++;
                }

            }
            else css=c+r-l+1-deg[a[r]];
            break;

        }

        int css2=0;
        rerun(css2,cand,a);

        printf("%d %d\n",css,css2);

    }


    return 0;
}