#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout<<"["<<#HEHE<<"] : ",dout(HEHE)
void dout(){cout<<'\n';}
template<typename T,typename...U>
void dout(T t,U...u){cout<<t<<(sizeof...(u)?", ":""),dout(u...);}
#else
#define debug(...) 7122
#endif

#define int long long
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1005;

int n, m;
vector<int> adj[SIZE];

struct BCC_BRIDGE {
    int dfcnt, bccnt;
    int dfn[SIZE], low[SIZE], bcc[SIZE];
    vector<int> st;

    void init() {
        dfcnt = bccnt = 0;
        st.clear();
        FOR (i, 1, n) dfn[i] = low[i] = bcc[i] = 0;
    }

    void tarjan (int pos, int fa) {
        dfn[pos] = low[pos] = ++dfcnt;
        st.pb (pos);
        for (int np : adj[pos]) if (np != fa) {
            if (!dfn[np]) {
                tarjan (np, pos);
                low[pos] = min (low[pos], low[np]);
                if (dfn[pos] < low[np]) {
                    bccnt++;
                    while (1) {
                        int x = st.back();
                        bcc[x] = bccnt;
                        st.pop_back();
                        if (x == np) break;
                    }
                }
            } else {
                low[pos] = min (low[pos], dfn[np]);
            }
        }
        if (pos == fa) {
            bccnt++;
            while (st.size()) {
                int x = st.back();
                bcc[x] = bccnt;
                st.pop_back();
            }
        }
    }
} bcc_b;

struct BCC_POINT {
    int dfcnt, bccnt;
    int dfn[SIZE], low[SIZE];
    vector<int> st, bcc[SIZE];

    void init() {
        dfcnt = bccnt = 0;
        st.clear();
        FOR (i, 1, n) dfn[i] = low[i] = 0, bcc[i].clear();
    }

    void tarjan (int pos, int fa) {
        dfn[pos] = low[pos] = ++dfcnt;
        st.pb (pos);
        for (int np : adj[pos]) if (np != fa) {
            if (!dfn[np]) {
                tarjan (np, pos);
                low[pos] = min (low[pos], low[np]);
                if (dfn[pos] <= low[np]) {
                    bccnt++;
                    while (1) {
                        int x = st.back();
                        bcc[x].pb (bccnt);
                        st.pop_back();
                        if (x == np) break;
                    }
                    bcc[pos].pb (bccnt);
                }
            } else {
                low[pos] = min (low[pos], dfn[np]);
            }
        }
    }
} bcc_p;

void solve() {
    cin >> n >> m;

    bcc_b.init();
    bcc_p.init();
    FOR (i, 1, n) adj[i].clear();

    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }

    bcc_b.tarjan (1, 1);
    bcc_p.tarjan (1, 1);

    int cnt = 0;
    FOR (i, 1, n) cnt += bcc_p.bcc[i].size() > 1;
    cout << cnt << ' ' << bcc_b.bccnt - 1 << ' ';

    int x, y = bcc_b.bccnt > 1;
    int sum[bcc_b.bccnt + 1] = {};
    x = bcc_b.bccnt - 1;
    FOR (i, 1, n) sum[bcc_b.bcc[i]]++;
    FOR (i, 1, bcc_b.bccnt) x += sum[i] >= 2;
    memset (sum, 0, sizeof (sum));
    FOR (i, 1, n) for (int j : adj[i]) sum[bcc_b.bcc[i]] += bcc_b.bcc[i] == bcc_b.bcc[j];
    y = max (y, *max_element (sum + 1, sum + bcc_b.bccnt + 1) / 2);
    int g = __gcd (x, y);

    cout << x / g << ' ' << y / g << '\n';
}

int32_t main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}