#pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#include<complex>
using namespace std;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM2
#define fi first
#define se second
typedef double ld;
const ll MAX = ll(1e6) + 100;
const ll INF = LLONG_MAX/10;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//public free to use template by bqi343 on github
struct mi {
 	ll v; explicit operator ll() const { return v; } 
	mi():v(0) {}
	mi(ll _v):v(ll(_v%MOD)) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // won't work for negative p
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }
bool operator==(mi a, mi b) { return a.v == b.v; }
bool operator==(mi a, ll b){ return a.v == b;}
ostream& operator<<(ostream& os, const mi& val)
{
    os << (ll) val;
    return os;
} 
ld epsilon =1e-12;
typedef complex<ld> pt;
#define x real()
#define y imag()
ld dot(pt a, pt b){
  return (conj(a)*b).x;
}
ld cross(pt a, pt b){
  return (conj(a)*b).y;
}
//Lazy Segment Tree supporting range assignment, range addition and range query


vector<vector<pair<ll,ll>>> adj;
const ll logn=21;
const ll maxn=1e5+100;
ll par[maxn][logn];
ll par_val[maxn][logn];
vector<bool> red; 
ll C[maxn];
ll tin[maxn],tout[maxn];
ll timer=0;
void dfs(ll v, ll p, ll cost,ll last){
  tin[v]=timer++;
  par[v][0]=p;
  par_val[v][0]=last;
  for(ll i=1;i<logn;i++){
    par[v][i]=par[par[v][i-1]][i-1];
  }
  for(ll i=1;i<logn;i++){
    par_val[v][i]=par_val[v][i-1]+par_val[par[v][i-1]][i-1];
  }
  if(red[v])cost=0;
  C[v]=cost;
  for(auto e: adj[v]){
    if(e.first==p)continue;
     dfs(e.first,v,cost+e.second,e.second);
  }
  tout[v]=timer++;
}
bool anc(ll u, ll v){
  return (tin[u]<=tin[v] and tout[u]>=tout[v]);
}
ll lca(ll u, ll v){
  if(anc(u,v))return u;
  if(anc(v,u))return v;
  for(ll i=logn-1;i>=0;i--){
    if(!anc(par[u][i],v))u=par[u][i];
  }
  return par[u][0];
}
ll diffCost(ll u, ll v){
  assert(anc(u,v));
  if(u==v)return 0;
  ll ans=0;
  for(ll i=logn-1;i>=0;i--){
    if(!anc(par[v][i],u)){ans+=par_val[v][i];v=par[v][i];}
  }
  return ans+par_val[v][0];
}
ll check(ll u, ll r){
  assert(anc(r, u));
  return min(C[u],diffCost(r,u));
}
void solve(){
  ll n,m;cin>>n>>m;
  vector<ll> deg(n,0);
  for(int i=0;i<m;i++){
    
    ll u,v;cin>>u>>v;
    u--;
    v--;
    deg[u]++;
    deg[v]++;
  }
  sort(deg.begin(),deg.end());
  reverse(deg.begin(),deg.end());
  ll sz=0;
  for(int  i=0;i<n;i++){
      if(deg[i]<i);
      else sz=i+1;
  }
  ll tot=0;
  for(int i=sz;i<n;i++){
    if(deg[i]==sz-1)tot++;
  }
  tot++;
  cout<<tot<<" ";
  // sz=n-sz;
  for(int i=0;i<n;i++){
    deg[i]=n-1-deg[i];
  }
  reverse(deg.begin(),deg.end());
  sz=0;
  for(int  i=0;i<n;i++){
      if(deg[i]<i);
      else sz=i+1;
  }
  tot=1;
  for(int i=sz;i<n;i++){
    if(deg[i]==sz-1)tot++;
  }
  cout<<tot<<"\n";

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t = 1;
    cin >> t;
    // ll  tt=1;
    // vector<ll> a(1e5+11,0);
    // seg.build(a);
    while(t--)
    {
        solve();}
    return 0;   
}