#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first	
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 17;
VI g[N];

int solve(int a, int b, VI vals)
{
	VI startSZ = vals;
	int n = SZ(vals);
	
	set<pair<PII, int>> vali;
	FOR(i, 0, n)
		vali.insert(MP(MP(vals[i], startSZ[i]), i));
			
	VI used(n, 0);
	int all = 0;
	while(true)
	{
		if(vali.begin()->F.F == vali.rbegin()->F.F && vali.begin()->F.F + all == SZ(vali) - 1)
			break;
	
	
		int v = vali.begin()->S;	
		vali.erase(vali.begin());
		used[v] = 1;
		all += a;			
		for(int to : g[v])
		{
			if(used[to])
				continue;
				
			vali.erase(MP(MP(vals[to], startSZ[to]), to));
			vals[to] += b;
			vali.insert(MP(MP(vals[to], startSZ[to]), to));
		}		
	}
		
	VI cnt(n, 0);
	all = 0;
	for(auto [_, v] : vali)
	{
		all -= a;
		for(int to : g[v])
		{
			if(used[to] == 0)
				continue;
				
			cnt[to] -= b;
		}
	}
	
	
	
	int ans = 1;
	FOR(i, 0, n)
	{
		if(used[i] == 1 && cnt[i] + all == SZ(vali) - 1)
			ans++;
	}
	
	return ans;
}



void solve()
{
	int n, m;
	cin >> n >> m;
	FOR(i, 0, m)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	VI vals(n);
	FOR(i, 0, n)
		vals[i] = SZ(g[i]);
	cout << solve(0, -1, vals) << " "; 

	FOR(i, 0, n)
		vals[i] = n - 1 - SZ(g[i]);	
	cout << solve(-1, 1, vals) << "\n"; 
	
	
	FOR(i, 0, n)
		g[i].clear();
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int t;
	cin >> t;
	while(t--)
		solve();
	
	
	
	return 0;
}