#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define F first 
#define S second 

const int mol=998244353;

int ans1=0, ans2=0;
const int N = 1005;
int haha[N][N];
struct yftree{
    vector<int>node[N],nnode[N*2];
    int vis[N],low[N],dfn[N],dep[N*2];
    stack<int>st;
    int nn=0,iu=0;
    int n;
    void init(int _n){
        n=_n;
        for(int i=1;i<=n;i++) node[i].clear(), nnode[i+n].clear(), nnode[i].clear(), vis[i]=0;
        while(st.size()) st.pop();
        nn=0, iu=0;
    }

    void add(int g,int h){
        node[g].pb(h);
        node[h].pb(g);
    }

    void dfs(int v,int pre){
        st.push(v);
        vis[v]=1;
        low[v]=dfn[v]=++iu;
        int c=0;
        bool ok=0;
        for(int k:node[v]){
            if(!vis[k]){
                c++;
                dfs(k,v);
                low[v]=min(low[v],low[k]);
                if(low[k]>=dfn[v]){
                    nn++;
                    if(v!=1)
                    ok=1;
                    int tt;
                    while(1){
                        tt=st.top();st.pop();
                        nnode[nn+n].pb(tt);
                        nnode[tt].pb(nn+n);
                        if(tt==k) break;
                    }
                    tt=v;
                    nnode[nn+n].pb(tt);
                    nnode[tt].pb(nn+n);
                }
            }
            else{
                low[v]=min(low[v],dfn[k]);
            }
        }
        if(v!=1&&ok) ans2++;
        if(v==1&&c>1) ans2++;
    }

    void work(int n){
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                int pre = iu;
                dfs(i, i);
                if(iu == pre + 1){
                    nn++;
                    nnode[nn+n].pb(i);
                    nnode[i].pb(nn+n);
                }
            }
        }
    }
}iu;
struct bcc_edge{
    vector<int>node[N+1], nnode[N+1], bcc[N+1];
    bool vis[N+1]={0};
    int id[N+1], dfn[N+1], low[N+1];
    stack<int>now;
    int iu=0;
    int num=0;

    void init(int _n){
        for(int i=1;i<=_n;i++) node[i].clear(), bcc[i].clear(), nnode[i].clear(), vis[i]=0;
        iu=0, num=0;

        while(now.size()) now.pop();
    }

    void add(int g,int h){
        node[g].pb(h);
        node[h].pb(g);
    }
    

    void dfs(int v,int pre){
        dfn[v]=low[v]=++iu;
        now.push(v);
        vis[v]=1;
        int cc=0;
        for(int k:node[v]){
            if(k==pre&&cc==0) {
                cc++;
                continue;
            }
            if(!vis[k]) {
                dfs(k, v);
                low[v]=min(low[v],low[k]);
            }
            else low[v]=min(low[v],dfn[k]);
        }
        if(low[v]==dfn[v]){
            num++;
            ans1++;
            if(v==1) ans1--;
            while(1){
                int t = now.top();
                now.pop();
                bcc[num].pb(t);
                if(t==v) break;
            }
        }
    }

    void work(int n){
        for(int i=1;i<=n;i++){
            if(!vis[i]) dfs(i, i);
        }
    }
}iu2;
void solve(){
    int n, m;
    cin>>n>>m;
    iu.init(n), iu2.init(n);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) haha[i][j]=0;
    ans1=0, ans2=0;
    
    while(m--){
        int g, h;
        cin>>g>>h;
        haha[g][h]=1;
        iu.add(g, h);
        iu2.add(g, h);
    }
    iu.work(n), iu2.work(n);
    int cnt=iu.nn;
    int iuu=0;
    for(int i=1;i<=cnt;i++){
        int an=0;
        for(int j=0;j<iu.nnode[i+n].size();j++){
            for(int k=j;k<iu.nnode[i+n].size();k++){
                if(haha[iu.nnode[i+n][j]][iu.nnode[i+n][k]]||haha[iu.nnode[i+n][k]][iu.nnode[i+n][j]]) an++;
            }
        }
        iuu=max(iuu, an);
    }
    int gg=__gcd(cnt, iuu);
    cnt/=gg, iuu/=gg;

    cout<<ans2<<" "<<ans1<<" "<<cnt<<" "<<iuu<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}