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

typedef long long ll; typedef unsigned long long ull;
const int inf = 1e9; const ll llnf = 4e18;

template< class Tp > void chkmax( Tp &x , Tp y ) { x = max( x , y ); }
template< class Tp > void chkmin( Tp &x , Tp y ) { x = min( x , y ); }

void solve( ) {
	int n , m; cin >> n >> m;
	vector< set< int > > G( n + 1 ); vector< int > deg( n + 1 ); for( int i = 1; i <= m; i ++ ) { int u , v; cin >> u >> v; G[u].emplace( v ) , G[v].emplace( u ); deg[u] ++ , deg[v] ++; }

	vector< vector< int > > S( n + 1 ); for( int u = 1; u <= n; u ++ ) S[deg[u]].emplace_back( u );
	vector< int > P;
	for( int d = n; d >= 0; d -- ) {
		bool bad = false;
		for( int i = 0; i < ( int ) S[d].size( ) && !bad; i ++ ) {
			for( int j = 0; j < ( int ) P.size( ) && !bad; j ++ ) if( !G[S[d][i]].count( P[j] ) ) bad = true;
			for( int j = i + 1; j < ( int ) S[d].size( ) && !bad; j ++ ) if( !G[S[d][i]].count( S[d][j] ) ) bad = true;
		}
		if( !bad ) for( int u : S[d] ) P.emplace_back( u );
		else {
			for( int u : S[d] ) {
				bad = false;
				for( int j = 0; j < ( int ) P.size( ) && !bad; j ++ ) if( !G[u].count( P[j] ) ) bad = true;
				if( !bad ) P.emplace_back( u );
			}
			break;
		}
	}
	vector< bool > grp( n + 1 ); for( int u : P ) grp[u] = true;

	int ans1 = 1;
	for( int u = 1; u <= n; u ++ ) if( !grp[u] ) {
		int bad = 0;
		for( int j = 0; j < ( int ) P.size( ) && bad <= 1; j ++ ) if( !G[u].count( P[j] ) ) bad ++;
		if( bad <= 1 ) ans1 ++;
	}

	vector< int > c( n + 1 ); for( int v = 1; v <= n; v ++ ) if( !grp[v] ) c[v] = -1;
	for( int u = 1; u <= n; u ++ ) if( !grp[u] ) for( int v : G[u] ) if( grp[v] ) c[v] ++;
	int ans2 = ( count( c.begin( ) + 1 , c.begin( ) + n + 1 , 0 ) > 0 ) ? ( count( c.begin( ) + 1 , c.begin( ) + n + 1 , 0 ) ) : ( 1 + count( c.begin( ) + 1 , c.begin( ) + n + 1 , 1 ) );

	cout << ans1 << " " << ans2 << "\n";
}

int main( ) {
	ios::sync_with_stdio( 0 ), cin.tie( 0 ), cout.tie( 0 );
	int T; cin >> T; while( T -- ) solve( ); return 0;
}