#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int TC, N, M;
vector<int> adj[MAXN+10], V[MAXN+10];
bool vis[MAXN+10];
int col[MAXN+10];

int main()
{
    scanf("%d", &TC);
    while(TC--)
    {
        scanf("%d%d", &N, &M);
        for(int i=1; i<=M; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        for(int i=1; i<=N; i++) V[adj[i].size()].push_back(i);

        int amax=0, bmin=N-1;

        bool flag=true;
        for(int i=0; i<N; i++)
        {
            for(auto u : V[i])
            {
                for(auto v : adj[u]) if(vis[v]) flag=false;
                vis[u]=true;
            }
            if(!flag) break;
            amax=i;
        }

        for(int i=1; i<=N; i++) vis[i]=false;
        int cnt=0; flag=true;
        for(int i=N-1; i>=0; i--)
        {
            for(auto u : V[i])
            {
                int t=0;
                for(auto v : adj[u]) if(vis[v]) t++;
                if(t!=cnt) flag=false;
                vis[u]=true; cnt++;
            }
            if(!flag) break;
            bmin=i;
        }
        if(amax+1>=bmin)
        {
            for(int i=1; i<=N; i++)
            {
                if(adj[i].size()<=amax) col[i]=1;
                else col[i]=2;
            }
        }
        else
        {
            assert(amax+2==bmin);

            vector<array<int, 4>> V;
            int sa=0, sb=0, sc=0;
            for(int i=1; i<=N; i++)
            {
                if(adj[i].size()<=amax) col[i]=1, sa++;
                else if(adj[i].size()>=bmin) col[i]=2, sb++;
                else col[i]=3, V.push_back({i, 0, 0, 0});
            }

            int p=0, q=0, r=0;
            for(auto &[u, ca, cb, cc] : V)
            {
                for(auto v : adj[u])
                {
                    if(col[v]==1) ca++;
                    else if(col[v]==2) cb++;
                    else cc++;
                }
                if(ca==0) p++;
                if(cb==sb) q++;
                r+=cc;
            }
            r/=2;

            for(auto [u, ca, cb, cc] : V)
            {
                if(ca==0 && q-(cb==sb)==V.size()-1 && r-cc==(ll)(V.size()-1)*(V.size()-2)/2)
                {
                    col[u]=1;
                    for(auto [v, ca, cb, cc] : V) if(v!=u) col[v]=2;
                    break;
                }

                if(cb==sb && p-(ca==0)==V.size()-1 && r==cc)
                {
                    col[u]=2;
                    for(auto [v, ca, cb, cc] : V) if(v!=u) col[v]=1;
                    break;
                }
            }
        }

        int sa=0, sb=0;
        for(int i=1; i<=N; i++)
        {
            if(col[i]==1) sa++;
            else sb++;
        }

        int sum=0;
        for(int i=1; i<=N; i++) if(col[i]==1 && adj[i].size()==sb) sum++;
        if(sum) printf("%d ", sum);
        else
        {
            for(int i=1; i<=N; i++) if(col[i]==1 && adj[i].size()==sb-1) sum++;
            printf("%d ", sum+1);
        }

        sum=0;
        for(int i=1; i<=N; i++) if(col[i]==2 && adj[i].size()==sb-1) sum++;
        if(sum) printf("%d\n", sum);
        else
        {
            for(int i=1; i<=N; i++) if(col[i]==2 && adj[i].size()==sb) sum++;
            printf("%d\n", sum+1);
        }

        for(int i=0; i<=N; i++)
        {
            adj[i].clear();
            V[i].clear();
            vis[i]=col[i]=0;
        }
    }
}