#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int h[N],e[N],ne[N],idx;
int n,m;
int dfn[N],low[N],lbr;
int dcccnt;
int st[N],tt=-1;
bool tf[N];//是否为割点
int ans;
int sz[N];

int stk[N];
int id[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int d[1010];

void tarjan(int x,int fa){
    dfn[x]=low[x]=++lbr;
    int c=0;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            c++;
            tarjan(j,x);
            low[x]=min(low[x],low[j]);
            if(fa!=x&&low[j]>=dfn[x]&&!tf[x]){
                ans++,tf[x]=1;
            }
        }else if(fa!=j){
            low[x]=min(low[x],dfn[j]);
        }
    }
    if(c>=2&&fa==x&&!tf[x]){
        tf[x]=1;
        ans++;
    }
}


void tarjan2(int x,int fa){
    dfn[x]=low[x]=++lbr;
    stk[++tt]=x;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan2(j,i);
            low[x]=min(low[x],low[j]);
            if(dfn[x]<low[j]){
                tf[i]=tf[i^1]=1;
            }
        }else if(i!=(fa^1)){
            low[x]=min(low[x],dfn[j]);
        }
    }
    if(dfn[x]==low[x]){
        ++dcccnt;
        int y;
        do{
            
            y=stk[tt--];
            id[y]=dcccnt;
            sz[dcccnt]++;
        }while(y!=x);
    }
}


void __(){
    
    cin>>n>>m;
    memset(h,-1,sizeof h);
    idx=0;
    tt=-1;
    lbr=0;
    ans=0;
    dcccnt=0;
    vector<pair<int,int> > vv;
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        vv.push_back({a,b});
        add(a,b),add(b,a);
    }
    
    memset(dfn,0,sizeof dfn);
    memset(id,0,sizeof id);
    memset(low,0,sizeof low);
    memset(tf,0,sizeof tf);
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,i);
    }
    
    cout<<ans<<" ";
    dcccnt=0;
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(sz,0,sizeof sz);
    memset(id,0,sizeof id);
    memset(tf,0,sizeof tf);
    tt=-1;
    lbr=0;
    for(int i=1;i<=n;i++){
        // cout<<"--"<<dfn[i]<<" ";
        if(!dfn[i]) tarjan2(i,i);
    }
    // cout<<endl;
    ans=0;
    for(int i=0;i<=m*2;i++) ans+=tf[i];
    cout<<ans/2<<" ";
    int ans3=0,ans4=0;
    // cout<<dcccnt<<endl;
    for(int i=1;i<=dcccnt;i++) if(sz[i]!=1) ans3++;
    ans3+=ans/2;
    map<int,int> mp;
    for(auto [x,y]:vv){
        int a=id[x],b=id[y];
        if(a==b) mp[a]++;
    }
    for(auto [x,y]:mp) ans4=max(ans4,y);
    // cout<<ans4<<endl;
    if(ans4==0) ans4=1;
    int gg=__gcd(ans3,ans4);
    cout<<ans3/gg<<" "<<ans4/gg<<endl;
}


int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
    
}