#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e5 + ;

struct Edge {

    int u, v, tonext;

}e[maxn * ], tree[maxn * ];

int first[maxn], num;

int first_tree[maxn], num_tree;

void addEdge(int u, int v) {

    ++num;

    e[num].u = u, e[num].v = v, e[num].tonext = first[u];

    first[u] = num;

}

int DFN[maxn], low[maxn], when, st[maxn], top;

int id[maxn], toSelid;

bool vis[maxn];

void tarjan(int cur, int fa) {

    DFN[cur] = low[cur] = ++when;  //时间戳

    st[++top] = cur; //进栈

    vis[cur] = true;

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (v == fa) continue;

        if (!DFN[v]) { //没访问过

            tarjan(v, cur);

            low[cur] = min(low[cur], low[v]);

        } else if (vis[v]) { // 访问过，而且还在栈里

            low[cur] = min(low[cur], DFN[v]);

        }

    }

    if (low[cur] == DFN[cur]) { //这个是强连通分量的根节点。

        ++toSelid;

        do {

            id[st[top]] = toSelid;      //块id

//            sum[toSelId]++;        //id节点个数

//            printf("%d ", st[top]);

            vis[st[top]] = false;

            top--;

        } while (cur != st[top + ]);

//        printf("\n");

    }

}

void solveTarjan(int n) {

    memset(DFN, , sizeof DFN);

    memset(low, , sizeof low);

    memset(vis, , sizeof vis);

    when = top = toSelid = ;

    for (int i = ; i <= n; ++i) {

        if (!DFN[i]) tarjan(i, i);

    }

}

void addEdgeTree(int u, int v) {

    ++num_tree;

    tree[num_tree].u = u, tree[num_tree].v = v, tree[num_tree].tonext = first_tree[u];

    first_tree[u] = num_tree;

}

struct bfsnode {

    int cur, cnt;

    bfsnode(int _cur, int _cnt) {

        cur = _cur;

        cnt = _cnt;

    }

};

int tree_diameter(int begin, bool flag) {

    memset(vis, , sizeof vis);

    queue<struct bfsnode> que;

    while (!que.empty()) que.pop();

    que.push(bfsnode(begin, ));

    vis[begin] = true;

    int to = begin, mx = ;

    while (!que.empty()) {

        struct bfsnode t = que.front();

        que.pop();

        for (int i = first_tree[t.cur]; i; i = tree[i].tonext) {

            int v = tree[i].v;

            if (vis[v]) continue;

            vis[v] = true;

            que.push(bfsnode(v, t.cnt + ));

            if (mx < t.cnt + ) {

                to = v;

                mx = t.cnt + ;

            }

        }

    }

    if (flag) return mx;

    else return to;

}

void work() {

    memset(first, , sizeof first);

    memset(first_tree, , sizeof first_tree);

    num = num_tree = ;

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        addEdge(u, v);

        addEdge(v, u);

    }

    solveTarjan(n);

//    for (int i = 1; i <= n; ++i) {

//        cout << id[i] << " ";

//    }

    for (int i = ; i <= n; ++i) {

        for (int j = first[i]; j; j = e[j].tonext) {

            int v = e[j].v;

            if (id[i] == id[v]) continue;

            addEdgeTree(id[i], id[v]);

            addEdgeTree(id[v], id[i]);

        }

    }

    int res = tree_diameter(, );

    int di = tree_diameter(res, );

    int ans = toSelid - di - ;

    ans = max(ans, );

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}