#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define i1 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define all(v) v.begin(), v.end()

using namespace std;

template<typename types>
void read(types &x) {
    x = 0; char c = getchar(); int f = 1;
    while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x *= f; return;
}
void read() {}
template<typename types, typename... Args>
void read(types &x, Args&... args) {
    read(x), read(args...);
    return;
}
template<typename types>
void write(types x) {
    if (x < 0) putchar('-'), x = -x;
    types k = x / 10;
    if (k) write(k);
    putchar(x - k * 10 + '0');
    return;
}
void print() { puts(""); }
template<typename types, typename... Args>
void print(types x, Args... args) {
    write(x), putchar(' '), print(args...);
    return;
}

const int MAXN = 1e5 + 10;

int n, m;
int T;
vector<int> to[MAXN];
int deg[MAXN], d[MAXN];

void solve() {
    read(n, m);
    for (int i = 1; i <= n; ++i) to[i].clear();
    fill(deg + 1, deg + n + 1, 0);
    fill(d + 1, d + n + 1, 0);
    for (int i = 1; i <= m; ++i) {
        int x, y; read(x, y);
        to[x].eb(y), to[y].eb(x);
        ++deg[x], ++deg[y];
    }
    if (!m) {
        write(n), putchar(' '), write(1), puts("");
        return;
    }
    vector<int> v(n);
    iota(all(v), 1), sort(all(v), [&] (int x, int y) { return deg[x] < deg[y]; });
    int k = -1;
    for (int i = n, j = n - 1; i; --i) {
        while (j >= 0 && deg[v[j]] >= i - 1) --j;
        if (n - 1 - j >= i) { k = i; break; }
    }
    assert(~k);
    int rem = n;
    for (int x : v) {
        if (deg[x] >= k - 1) break;
        --rem;
        for (int y : to[x]) --deg[y], ++d[y];
    }
    int cnt = 0; for (int i = 1; i <= n; ++i) cnt += deg[i] >= k;
    int A = 0, B = 0;
    // cerr << "K: " << k << ' ' << cnt << ' ' << rem << endl;
    int cs = 0;
    if (!cnt) {
        A = 1;
        int c[3] = {};
        for (int i = 1; i <= n; ++i)
            if (deg[i] >= k - 1 && d[i] <= 2) ++c[d[i]];
        if (c[0]) B = c[0];
        else B = c[1] + 1;
    }
    else if (cnt == k - 1) {
        cs = 1;
        int ex = -1;
        for (int i = 1; i <= n; ++i)
            if (deg[i] == k - 1 && d[i]) ex = i;
        if (~ex) {
            A = 1;
            if (d[ex] == 1) B = 2;
            else B = 1;
        }
        else {
            A = rem - (k - 1);
            B = 1;
        }
    }
    else {
        cerr << "CNT: " << cnt << ' ' << k << endl;
        cs = 2;
        assert(cnt == k);
        A = 1;
        for (int x : v) {
            if (deg[x] == k - 1)
                for (int y : to[x]) --deg[y], ++d[y];
        }
        int c = 0;
        for (int x : v) 
            if (deg[x] >= k && d[x] == 1) ++c; 
        B = c + 1;
    }
    if (T == 1013) {
        cout << n << ' ' << m << ' ' << cs << endl;
    }
    write(A), putchar(' '), write(B), puts("");
    return;
}

int main() {
    int t; read(t);
    while (t--) ++T, solve();
    return 0;
}