#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { if(a <= b) return 0; a = b; return 1; }
bool chmax(auto& a, auto b) { if(a >= b) return 0; a = b; return 1; }


void solve() {
    ll N, M;
    cin >> N >> M;
//    if(M == 0) return {N, 1};
    vector<set<ll>> g(N);
    vector<ll> deg(N);
    vector<pair<ll, ll>> edge(M);
    for(auto& [A, B] : edge) {
        cin >> A >> B;
        A--; B--;
        g[A].insert(B);
        g[B].insert(A);
        deg[A]++;
        deg[B]++;
    }
    vector<ll> cl, ind, pend;
    rep(i, 0, N) pend.push_back(i);
    ranges::sort(pend, {}, [&](ll i) { return deg[i]; });
    while(sz(pend)) {
        const ll i = pend.back();
        pend.pop_back();
        cl.push_back(i);
        vector<ll> A, B;
        for(ll j : pend) (g[i].contains(j) ? A : ind).push_back(j);
        pend = move(A);
    }
    vector<bool> is_cli(N);
    for(ll i : cl) is_cli[i] = 1;
    
    vector<ll> D(N);
    for(auto [i, j] : edge) {
        if(is_cli[i] and is_cli[j]) continue;
        D[i]++;
        D[j]++;
    }
    
    vector<ll> D1, D0;
    rep(i, 0, N) (is_cli[i] ? D1 : D0).push_back(D[i]);
    cout << [&] {
        if(ranges::count(D0, sz(cl))) return ranges::count(D0, sz(cl));
        return 1 + ranges::count(D0, sz(cl) - 1);
    }() << ' ' << [&]{
        if(ranges::count(D1, 0)) return ranges::count(D1, 0);
        return 1 + ranges::count(D1, 1);
    }() << '\n';
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin >> T;
    while(T--) solve();
}