#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define all(a) a.begin(), a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto& b) {return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto& b) {return a < b ? a = b, 1 : 0; }

void solve() {
	int n,m;
	cin >> n >> m;
	vvp G(n);
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		G[u].eb(v, i);
		G[v].eb(u, i);
	}
	vl ls;
	vl cmp;
	int art = 0, brd = 0;
	int k = 0;
	vl ord(n, -1), low(n, -1);
	auto dfs = [&](auto &dfs, int u, int p) -> void {
		ord[u] = low[u] = k++;
		bool flag = false;
		int cnt = 0;
		for(auto [v,id] : G[u]) {
			if(ord[v] < 0) {
				ls.eb(id);
				++cnt;
				dfs(dfs, v, u);
				chmin(low[u], low[v]);
				if(low[v] > ord[u]) ++brd;
				if(low[v] >= ord[u]) {
					if(p >= 0) flag = true;
					set<ll> st;
					while(true) {
						assert(!ls.empty());
						int e = ls.back();
						st.insert(e);
						ls.pop_back();
						if(e == id) break;
					}
					cmp.eb(SZ(st));
				}
			} else if(v != p) {
				if(ord[v] < ord[u]) ls.eb(id);
				chmin(low[u], ord[v]);
			}
		}
		flag |= p < 0 and cnt > 1;
		if(flag) ++art;		
	};
	dfs(dfs, 0, -1);
	int p = SZ(cmp);
	int q = *max_element(all(cmp));
	int g = gcd(p, q);
	cout << art << ' ' << brd << ' ' << p/g << ' ' << q/g << '\n';
}
	

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	rep(_, t) solve();
}