#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll
#define fi first
#define se second
#define pb push_back

const int N = 200500;
const int C = 500;
vector<int> g[N];
int n;
int l[N];
int dp[N];

int calc(int v)
{
    if (dp[v] != -1)
        return dp[v];
    for (int i=1; i<=n; i++)
        l[i] = -1;
    l[v] = 0;
    queue<int> q;
    q.push(v);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (int i : g[v])
            if (l[i] == -1)
        {
            l[i] = l[v] + 1;
            q.push(i);
        }
    }
    int s = 0;
    for (int i=1; i<=n; i++)
        s += l[i];
    return dp[v] = s;
}

mt19937 rng(time(0));

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

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

    pair<int, int> ans;
    ans.fi = 1e18;
    for (int i=1; i<=C; i++)
    {
        int v = rng()%n+1;
        ans = min(ans, {calc(v), v});
    }

    int v = ans.se;
    int cur = ans.fi;
    shuffle(g[v].begin(), g[v].end(), rng);
    int ptr = 0;
    for (int i=1; i<=C; i++)
    {
        if (ptr == g[v].size())
            break;
        int u = g[v][ptr];
        int nt = calc(u);
        if (nt < cur)
        {
            cur = nt;
            v = u;
            ptr = 0;
            shuffle(g[v].begin(), g[v].end(), rng);
        }
        ptr++;
    }
    cout<<cur<<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;
    while (t--)
        solve();
}