include<bits/stdc++.h>

define pb push_back

define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

define ll long long

define pii pair<int,int>

define pll pair<ll,ll>

define f first

define s second

define int long long

define sz(x) (ll)(x.size())

using namespace std;

const int mod = 1e9+7;

int expo_pow(int x,int y){ if(y == 0) return 1; y=y%(mod-1); x%=mod; if(y==0) y=mod-1; int res=1; while(y){ if(y&1) res=(res*x)%mod; x=(x*x)%mod; y>>=1; } return res; }

ll add() { return 0; }

template <typename T, typename... Types> T add(T var1, Types... var2){ return (((((ll)(var1)) % mod + (ll)(add(var2...))) % mod) + mod) % mod; }

ll mul(){ return 1; }

template <typename T, typename... Types> T mul(T var1, Types... var2){ return (((ll)(var1)) % mod * (ll)(mul(var2...))) % mod; }

int n,m; vector<vector> adj; int cnt_cric,bridges; vector<vector> adj2; vector visited; vector tin,low; vector is_cut; int timer,comp,mx_comp; int cur_comp; int cut_count = 0; vector<vector> done;

void init() { adj.clear(); adj.resize(n+1); adj2.clear(); adj2.resize(n+1); tin.clear(); tin.resize(n+1); low.clear(); low.resize(n+1); visited.clear(); visited.assign(n+1,0); is_cut.clear(); is_cut.assign(n+1,0); done.clear(); done.assign(n+1,vector(n+1,0)); cnt_cric = 0; bridges = 0; timer = 0; comp = 0; mx_comp = 0; }

void dfs(int v,int p = -1) { visited[v] = 1; tin[v] = low[v] =timer++; int children = 0;

for (auto u:adj[v]) { if (u == p) continue; if (visited[u]) { if (done[u][v] == 0) { adj2[u].pb(v); adj2[v].pb(u); done[u][v] = 1; done[v][u] = 1; } low[v] = min(tin[u],low[v]); } else { dfs(u,v); low[v] = min(low[u],low[v]);

if (low[u] >= tin[v] and p != -1) {
    is_cut[v] = 1;
  }
  if (low[u] > tin[v]) {
    bridges++;
  } else {
    if (done[u][v] == 0) {
      adj2[u].pb(v);
      adj2[v].pb(u);
      done[u][v] = 1;
      done[v][u] = 1;
    }
  }

  ++children;
}

}

if (p == -1 and children > 1) { is_cut[v] = 1; } }

void dfs2(int cur,int par = -1) { if (is_cut[cur] == 1 and cut_count == 0){ cut_count++; return; } visited[cur] = 1; for (auto u:adj2[cur]) { if (u == par) continue; if (visited[u] == 1) { if (done[u][cur] == 0) { cur_comp++; done[u][cur] = 1; done[cur][u] = 1; } } else { dfs2(u,cur); if (done[u][cur] == 0) { cur_comp++; done[u][cur] = 1; done[cur][u] = 1; } } } }

void solve(){

cin >> n >> m; init(); for (int i = 0; i < m; ++i) { int p,q; cin >> p >> q; adj[p].pb(q); adj[q].pb(p); }

dfs(1);

visited.clear(); visited.assign(n+1,0); done.assign(n+1,vector(n+1,0)); for (int i = 1; i <= n; ++i) { if (visited[i] == 0 and is_cut[i] == 0) { cut_count = 0; cur_comp = 0; dfs2(i); mx_comp = max(cur_comp,mx_comp); if(cur_comp != 0) comp++; } }

for (int i = 1; i <= n; ++i) { if (is_cut[i]) cnt_cric++; }

int p = max(1LL,comp + bridges); int q = max(1LL,mx_comp); int g = __gcd(p,q); p /= g; q /= g; cout << cnt_cric << " " << bridges << " " << p << " " << q << "\n"; }

signed main(){ fast; int test = 1; cin>>test; int i=1; while(test--){ solve(); } }