#include<bits/stdc++.h>

using namespace std;
const int maxm = 2e5+7;
vector<int>edge[maxm];
int inv[maxm],inA[maxm],inB[maxm];//描述一个点在A中
int a[maxm];
void solve(){
    int n,m,u,v,sa = 0,sb = 0;
    // 设最大团为A,最大独立集为B
    // 首先，度数更大的点一定是在A中
    // 若u,v之间有连边，则u、v不可能同时在B中
    // 下面来思考一个问题，度数更大的点一定会在A中吗？
    // 如果这个点在B中的话，那么与之相连的所有的点都要在A中
    // 这说明这些点两两之间是有连边的
    // 那么我们便可以将这个点也加入到A中
    // 假设A的大小为|A|,则B中的点的度数至多为|A|-1
    // 所以度数大的点一定会在A中
    // 按照度数从大到小依次加入即可
    // 可以直接遍历，遍历的复杂度不会太大
    // 在求解最大独立集时，不能按照原有的划分去求
    // 思考这样一个事实，是否从按照度数从小到大加入即可？
    // 较小的点一定会在B中吗？
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        a[i] = i;
        inv[i] = inA[i] = inB[i] = 0;
        edge[i].clear();
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
        inv[u]++,inv[v]++;
    }
    sort(a+1,a+n+1,[&](int x,int y){return inv[x]>inv[y];});
    sa = 1,inA[a[1]] = 1;
    for(int i=2;i<=n;i++){
        //看编号为i的点能否在A集合中
        int now = 0;
        for(auto u:edge[a[i]]){
            if(inA[u]) ++now;
        }
        if(now == sa){
            ++sa;inA[a[i]] = 1;
        }
        else break;
    }
    int ans = 1,ans2 = 1;
    for(int i=1;i<=n;i++){
        if(inA[i]) continue;
        if(inv[i] == sa - 1) ++ans;
    }
    //计算出了最大团的数量
    //下面考虑最大独立集的数量
    sort(a+1,a+n+1,[&](int x,int y){return inv[x]<inv[y];});
    sb = 1,inB[a[1]] = 1;
    for(int i=2;i<=n;i++){
        //看编号为i的点能否在A集合中
        int now = 1;
        for(auto u:edge[a[i]]){
            if(inB[u]) now = 0;
        }
        if(now){
            ++sb;inB[a[i]] = 1;
        }
        else break;
    }
    for(int i=1;i<=n;i++){
        if(inB[i]) continue;
        int now = 0;
        for(auto u:edge[i]){
            if(inB[u]) ++now;
        }
        if(now == 1) ++ans2;
    }
    cout<<ans<<" "<<ans2<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}