#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long int ll;
#define INF LLONG_MAX

vector<bool> visited(100005);
vector<ll> adj[100005];
vector<ll> dist(100005);
ll n,m,u,v;
ll c = 0;
ll big = -INF;
ll sum;

void dfs(ll s){

    if(visited[s] == true) return;
    visited[s] = true;
    c++;
    big = max(big , s);
    for(auto u : adj[s]) if(visited[u] == false ) dfs(u);
}

void bfs(ll s){

    queue<ll> q;
    for(ll i = 0; i < n; i++) {
        dist[i] = 0;
        visited[i] = false;
    }
    q.push(s);
    dist[s]  = 1;
    sum = 1;
    while(!q.empty()){
        ll a = q.front();
        q.pop();
        if(visited[a] == true) continue;
        visited[a] = true;

        for(auto x : adj[a]){
            if(visited[x] == true) continue;
            q.push(x);
            dist[x] = dist[a] + 1;
            sum += dist[x];
        }
    }
}


int main() {

    fastio;

    ll test;
    cin >> test;

    while(test--){

        queue<ll> o;
        queue<ll> e;
        ll powerodd = 0 , powereven = 0;

        cin >> n >> m;
        for(ll i = 0; i < m; i++){
            cin >> u >> v;
            adj[u-1].push_back(v-1);
            adj[v-1].push_back(u-1);
        }
        for(ll i = 0; i < n; i++){
            if(visited[i] == true) continue;
            c = 0;
            big = -INF;
            dfs(i);
            if(c%2 == 0) e.push(i);
            else o.push(big);
        }

        while(!e.empty()){

            ll a = e.front();
            e.pop();
           sum = 0;

            bfs(a);
            powereven += sum;

        }

        while(!o.empty()){

            ll b = o.front();
            o.pop();
            sum  = 0;
            bfs(b);
            powerodd += sum;
        }

        cout << powereven << " " << powerodd << "\n";

        for(ll i = 0; i < n; i++) {
            adj[i].clear();
            visited[i] = false;
        }
    }
    return 0;
}