#include <bits/stdc++.h>
int T, n, m, rk[100005], maxA, cntA, maxB, cntB;
bool in[100005];
std::vector<int> to[100005];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> T;
    while (T--)
    {
        std::cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            to[i].clear(), rk[i] = i;
        for (int i = 1, u, v; i <= m; ++i)
        {
            std::cin >> u >> v;
            to[u].push_back(v);
            to[v].push_back(u);
        }
        std::sort(rk + 1, rk + 1 + n, [&](const int &A, const int &B)
                  { return to[A].size() < to[B].size(); });
        maxA = maxB = 0;
        std::fill(in + 1, in + 1 + n, false);
        for (int i = n; i; --i)
        {
            int cnt = 0;
            for (auto j : to[rk[i]])
                if (in[j])
                    ++cnt;
            if (cnt == n - i)
            {
                in[rk[i]] = true;
                ++maxA;
            }
        }
        std::fill(in + 1, in + 1 + n, false);
        for (int i = 1; i <= n; ++i)
        {
            bool flag = true;
            for (auto j : to[rk[i]])
                if (in[j])
                    flag = false;
            if (flag)
            {
                in[rk[i]] = true;
                ++maxB;
            }
        }
        cntA = cntB = 1;
        std::fill(in + 1, in + 1 + n, false);
        for (int i = n; i; --i)
            if (i > n - maxA)
                in[rk[i]] = true;
            else
            {
                int cnt = 0;
                for (auto j : to[rk[i]])
                    cnt += in[j];
                cntA += cnt == maxA - 1;
            }
        std::fill(in + 1, in + 1 + n, false);
        for (int i = 1; i <= n; ++i)
            if (i <= maxB)
                in[rk[i]] = true;
            else
            {
                int cnt = 0;
                for (auto j : to[rk[i]])
                    cnt += in[j];
                cntB += cnt == 1;
            }
        std::cout << cntA << ' ' << cntB << std::endl;
    }
    return 0;
}