#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

const int NMAX = 1e5 + 1;

vector<int> v[NMAX];

void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    v[i].clear();

  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }

  int mx = 0, wh = 1;
  for (int i = 1; i <= n; ++i) {
    if ((int)v[i].size() > mx)
      mx = v[i].size(), wh = i;
  }

  vector<int> pot(n + 1, 0);
  int nr = 1;
  priority_queue<pair<int, int>> pq;
  for (auto it : v[wh]) {
    pot[it] = nr;
    pq.push({v[it].size(), it});
  }

  vector<int> c;
  c.push_back(wh);
  while (!pq.empty()) {
    int nod = pq.top().second;
    pq.pop();
    if (pot[nod] != nr)
      continue;

    ++nr;
    c.push_back(nod);
    for (auto it : v[nod]) {
      if (pot[it] == nr - 1)
        pot[it] = nr;
    }
  }

  vector<int> inc(n + 1, 0);
  int sx = 0;
  int a1 = 0;
  for (auto nod : c) {
    sx ^= nod;
    inc[nod] = 1;

    if (v[nod].size() == c.size() - 1)
      ++a1;
  }

  if (a1 > 1) {
    cout << 1 << " " << a1 << '\n';
    return;
  }

  if (a1 == 0) {
    a1 = 1;
    for (auto nod : c) {
      if (v[nod].size() == c.size())
        ++a1;
    }
  }


  int a2 = 1;
  for (int i = 1; i <= n; ++i) {
    if (inc[i])
      continue;

    int cnt = 0;
    int mis = sx;
    for (auto it : v[i]) {
      if (inc[it]) {
        ++cnt;
        mis ^= it;
      }
    }

    if (cnt == c.size() - 1) {
      ++a2;
    }
  }

  cout << a2 << " " << a1 << '\n';
}

int main() {
#ifdef HOME
  ifstream cin("input.in");
  ofstream cout("output.out");
#endif
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  int t = 1;
  cin >> t;
  while (t--)
    solve();

  return 0;
}