#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
inline int read(){
    char ch=getchar();
    int x=0,f=1;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int MAXN=100010;
int n,m;
vector<int> G[MAXN];
int d[MAXN];
int deg[MAXN];
bool vis[MAXN];
bool check(int lim){
    int cnt=0;
    queue<int> q;
    for(int i=1;i<=n;++i){
        deg[i]=d[i];
        vis[i]=true;
        if(deg[i]<lim-1){
            vis[i]=false;
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        cnt++;
        for(auto v: G[u]){
            deg[v]--;
            if(deg[v]<lim-1&&vis[v]){
                vis[v]=false;
                q.push(v);
            }
        }
    }
    if(n-cnt<lim)return false;
    else return true;
}
vector<int> vec;
int ans1,ans2;
void gao(int lim){
    queue<int> q;
    for(int i=1;i<=n;++i){
        deg[i]=d[i];
        vis[i]=true;
        if(deg[i]<lim-1){
            vis[i]=false;
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(auto v: G[u]){
            deg[v]--;
            if(deg[v]<lim-1&&vis[v]){
                vis[v]=false;
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(vis[i]&&deg[i]>=lim)vec.push_back(i);
    }
    if(vec.size()==lim)return;
    else {
        for(int i=1;i<=n;++i){
            if(vis[i]&&deg[i]==lim-1){
                vec.push_back(i);
                if(vec.size()==lim){
                    for(int j=i+1;j<=n;++j){
                        if(vis[j]&&deg[j]==lim-1){
                            ans1++;
                        }
                    }
                    return;
                }
            }
        }
    }
    // for(int i=1;i<=n;++i)
    //     if(vis[i])vec.push_back(i);
    // int t=vec.size();
    // for(int u: vec){
    //     if(t==lim)break;
    //     if(deg[u]==lim-1){
    //         bool flag=1;
    //         for(int v: G[u]){
    //             if(deg[v]==lim-1){
    //                 flag=0;
    //                 break;
    //             }
    //         }
    //         if(flag){
    //             t--;
    //             vis[u]=false;
    //             for(int v: G[u]){
    //                 deg[v]--;
    //             }
    //         }
    //     }
    // }
    // vec.clear();
    // for(int i=1;i<=n;++i)
    //     if(vis[i]) vec.push_back(i);
}
int main(){
    // freopen("F.in","r",stdin);
    int T;
    cin>>T;
    int cnt=0;
    while(T--){
        cnt++;
        n=read(),m=read();
        rep(i,1,m){
            int u=read(),v=read();
            G[u].push_back(v),G[v].push_back(u);
            d[u]++,d[v]++;
        }
        int l=1,r=n;
        int ans=1;
        ans1=0,ans2=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        // cout<<ans<<endl;
        ans1=1;
        gao(ans);
        // for(auto x: vec){
        //     cout<<x<<' ';
        // }
        // cout<<endl;
        // rep(i,1,n){
        //     if(vis[i])continue;
        //     if(d[i]==ans-1){
        //         // cout<<i<<endl;
        //         for(auto x: G[i]){
        //             vis[x]=false;
        //         }
        //         for(auto x: vec){
        //             if(vis[x]&&d[x]==ans-1){
        //                 ans1++;
        //             }
        //             vis[x]=true;
        //         }
        //         for(auto x: G[i]){
        //             vis[x]=true;
        //         }
        //     }
        // }
        for(auto x: vec){
            if(d[x]==ans-1){
                ans2++;
            }
        }
        if(!ans2){
            for(auto x: vec){
                if(d[x]==ans){
                    ans2++;
                }
            }
            ans2++;
        }
        if(T<=3)printf("%d %d\n",ans1,ans2);
        else if(cnt==1021){
            cout<<n<<' '<<m<<endl;
            for(int i=1;i<=n;++i){
                for(auto v: G[i]){
                    if(i<v)cout<<i<<' '<<v<<endl;
                }
            }
        }
        rep(i,1,n){
            d[i]=deg[i]=0;
            G[i].clear();
            vis[i]=false;
        }
        vec.clear();
    }
}