#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; }


pair<ll, ll> 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)) {
        if(deg[pend[0]] == deg[pend.back()] && deg[pend[0]] == sz(cl)) break;
        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);
    }
    const ll a = max<ll>(1, sz(pend));
    vector<bool> is_cli(N);
    vector<ll> D(N, INF);
    for(ll i : cl) {
        is_cli[i] = 1;
        D[i] = 0;
    }
    for(auto [i, j] : edge) {
        if(is_cli[i] and is_cli[j]) continue;
        D[i]++;
        D[j]++;
    }
    const ll b = ranges::min(D) == 0 ? ranges::count(D, 0) : 1 + ranges::count(D, 1);
    return {a, b};
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin >> T;
    while(T--) {
        auto [a, b] = solve();
        cout << a << ' ' << b << '\n';
    }
}

/*
 1
 6 6
 1 2
 2 3
 1 3
 1 4
 2 5
 3 6

 
 */