#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
int bridge = 0,cut = 0;
vi num, st;
vector<vector<pii>> ed;
int Time;
int dfs(int at, int par, vector<vector<int>> &f){
    int me = num[at] = ++Time, e, y, top = me;
    for (auto pa : ed[at]) if (pa.second != par){
        tie(y, e) = pa;
        if (num[y]){
            top = min(top, num[y]);
            if (num[y] < me)
                st.push_back(e);
        }
        else {
            int si = sz(st);
            int up = dfs(y, e, f);
            top = min(top, up);
            if (up == me){
                st.push_back(e);
                f.push_back(vi(st.begin() + si, st.end()));
                st.resize(si);
            }   
            else if (up < me) st.push_back(e);
            else { bridge++;}
        }
    }
    return top;
}

int main()
{
    int t;
    cin>>t;
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    while(t--){
        bridge = cut = Time = 0;
        st.clear();
        num.clear();
        int n,m;
        cin>>n>>m;
        int eid = 0;
        ed.resize(n);
        for(int i=0;i<n;i++)ed[i].clear();
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            ed[a].push_back({b,eid});
            ed[b].push_back({a,eid++});
        }
        vector<vector<int>>v;
        num.assign(sz(ed),0);
        for(int i=0;i<n;i++)if(!num[i])dfs(i,-1,v);

        int mx = 1;    
        int id = 0;
        vector<int>lab(m,-1);
        for(auto x:v){ 
            mx = max(mx,sz(x));
            for(int y:x)lab[y] = id;
            id++;
        }
        
        vector<int>seen(m,0);
        for(int i=0;i<n;i++){
            int cnt = 0;
            for(pii x:ed[i]){
                int c = lab[x.second];
                if(c == -1)cnt++;
                else{
                    if(!seen[c])cnt++;
                    seen[c] = 1;
                }
            }
            for(pii x:ed[i]){
                int c = lab[x.second];
                if(c == -1)continue;
                else seen[c] = 0;
            }
            if(cnt>1)cut++;
        }
        int comp = sz(v);
        comp += bridge;
        int g = gcd(comp,mx);
        comp/=g;
        mx/=g;
        cout<<cut<<" "<<bridge<<" "<<comp<<" "<<mx<<'\n';
        //cout<<"TES"<<'\n';
    }

    return 0;
}