#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;
    int cnt = 0;
    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){
                //cout<<at<<" "<<y<<'\n';
                cnt++;
                if(par != -1)cut++;
                else if(cnt>1)cut++;
            }
            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();
        vector<array<int,2>>ee;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            ee.push_back({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<sz(ed);i++)if(!num[i])dfs(i,-1,v);

        vector<int>seen(n,0);
        int mx = 0;    
        for(auto x:v){ 
            mx = max(mx,sz(x));
        }
        int comp = sz(v);
        comp += bridge;
        int g = gcd(comp,mx);
        comp/=g;
        mx/=g;
        cout<<cut<<" "<<bridge<<" "<<comp<<" "<<mx<<'\n';
    }

    return 0;
}