#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 1e5 + 7 ;

int n , m ;
vector < int > v[ MAXN ] ;
int deg[ MAXN ] ;
pii srt[ MAXN ] ;
int wh[ MAXN ] ;

void solve ( ) {
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        v[ i ].clear ( ) , deg[ i ] = 0 ;
    }
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
        ++ deg[ x ] , ++ deg[ y ] ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        srt[ i ] = { deg[ i ] , i } ;
    }
    sort ( srt + 1 , srt + n + 1 , greater < pii > ( ) ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        wh[ srt[ i ].se ] = i ;
    }
    int mx = 1 ;
    bool done = false ;
    int mxsz = 0 ;
    for ( int ctr = 1 ; ctr <= n ; ++ ctr ) {
        int i = srt[ ctr ].se ;
        int cnt = 0 ;
        for ( auto j : v[ i ] ) {
            if ( wh[ j ] < wh[ i ] ) { ++ cnt ; }
        }
        if ( cnt == ctr - 1 ) { ++ mxsz ; continue ; }
        if ( cnt == mxsz - 1 ) { ++ mx ; }
    }
    int mn = n - mxsz , mn_cnt = 1 ;
    for ( int ctr = 1 ; ctr <= mxsz ; ++ ctr ) {
        int i = srt[ ctr ].se ;
        int cnt = 0 ;
        for ( auto j : v[ i ] ) {
            if ( mxsz < wh[ j ] ) { ++ cnt ; }
        }
        if ( cnt == 0 ) {
            if ( mn < n - mxsz + 1 ) {
                mn = n - mxsz + 1 ;
                mn_cnt = 0 ;
            }
            ++ mn_cnt ;
        }
        if ( cnt == 1 ) {
            if ( mn == n - mxsz ) { ++ mn_cnt ; }
        }
    }
    cout << mx << " " << mn_cnt << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}