#include <cassert>
#include <cstdint>
#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

constexpr int N = 2e5 + 1;

int d[N], st[N], sz[N], n;
int64_t ans;
vector<int> nei[N], tmp;

void build(int v, int p, int cd) {
  sz[v] = 1;
  d[v] = cd;
  for (auto u: nei[v]) if (u != p) if (!d[u]) {
    build(u, v, cd + 1);
    sz[v] += sz[u];
  }
}

int solve(int v) {
  st[d[v]] = v;
  int r = -1;
  for (auto u: nei[v]) if (d[u] == d[v] + 1) {
    int t = solve(u);
    if (!~t) ans += min(sz[u], n - sz[u]) * 2;
    else if (t != v) r = t;
  } else if (d[u] < d[v] - 1) {
    r = u;
    tmp.push_back(sz[v]);
    for (int i = d[v]; --i > d[u]; ) tmp.push_back(sz[st[i]] - sz[st[i + 1]]);
    tmp.push_back(n - sz[st[d[u] + 1]]);
    int s = 0;
    for (int i = 0; i < tmp.size() / 2; ++i) s += tmp[i];
    for (int i = 0; i < tmp.size() - tmp.size() / 2; ++i) ans += min(s, n - s), s += tmp[i + tmp.size() / 2] - tmp[i];
    for (int i = tmp.size() - tmp.size() / 2; i < tmp.size(); ++i) ans += min(s, n - s), s += tmp[i + tmp.size() / 2 - tmp.size()] - tmp[i];
    tmp.clear();
  }
  return r;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int tc = (cin >> tc, tc); tc--; ) {
    int m; cin >> n >> m;
    unordered_set<uint64_t> e;
    for (int i = 0; i < m; ++i) {
      int a, b; cin >> a >> b; --a, --b;
      if (a > b) swap(a, b);
      if (!e.insert(a + 0ull << 32 | b).second) continue;
      nei[a].push_back(b);
      nei[b].push_back(a);
    }
    assert(e.size() == m);
    build(0, 0, 1);
    solve(0);
    cout << ans / 2 << '\n';
    ans = 0;
    for (int i = 0; i < n; ++i) d[i] = 0, nei[i] = {};
  }
}