Bridge Tree

static const int maxn = 1e5 + 5;

struct node
{
    int v, e;
    node(int vv = 0, int ee = 0) : v(vv), e(ee) {}
};

vector <node> graph[maxn];
int dfsTime, dis[maxn], low[maxn];
bool isBridge[maxn], vis[maxn];
int totalBridge;

void findBridge(int u, int p = -1)
{
    vis[u] = 1;
    dis[u] = low[u] = dfsTime++;
    for (auto &it : graph[u])
    {
        int v = it.v;
        int e = it.e;
        if (v == p)
            continue;
        if (!vis[v])
        {
            findBridge(v, u);
            low[u] = min(low[u], low[v]);
            if (dis[u] < low[v])
            {
                isBridge[e] = 1;
                totalBridge++;
            }
        }
        else
        {
            low[u] = min(low[u], dis[v]);
        }
    }
}

int compo;
bool used[maxn];
vector <int> tree[maxn];


void bridgeTree(int src)
{
    used[src] = 1;
    int cur_compo = compo;
    queue <int> PQ;
    PQ.push(src);
    while(!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        for (auto &it : graph[u])
        {
            int v = it.v;
            int e = it.e;
            if (used[v])
                continue;
            if (isBridge[e])
            {
                compo++;
                tree[cur_compo].push_back(compo);
                tree[compo].push_back(cur_compo);
                bridgeTree(v);
            }
            else
            {
                PQ.push(v);
                used[v] = 1;
            }
        }
    }
}
int maxDis, maxDisNode;

void dfs(int u, int p, int d)
{
    if (d > maxDis)
    {
        maxDis = d;
        maxDisNode = u;
    }
    for (int v : tree[u])
    {
        if (v == u)
            continue;
        dfs(v, u, d+1);
    }
}

void init()
{
    dfsTime = 0;
    totalBridge = 0;
    compo = 1;
    for (int i = 0; i < maxn; i++)
    {
        vis[i] = 0;
        used[i] = 0;
        dis[i] = 0;
        low[i] = 0;
        isBridge[i] = 0;
        graph[i].clear();
        tree[i].clear();
    }
}

int main()
{
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        init();
        int n, m;
        cin >> n >> m;
        int src = n;
        for (int e = 1; e <= m; e++)
        {
             int u, v;
             cin >> u >> v;
             graph[u].push_back(v);
             graph[v].push_back(u);
             src = min(src, min(u, v));
        }
        findBridge(src);
        bridgeTree(src);
        maxDis = -1;
        maxDisNode = -1;
        dfs(1, -1, 0);
        maxDis = -1;
        dfs(maxDisNode, -1, 0);
        cout << (totalBridge � maxDis) << endl;
    }
}  static const int maxn = 1e5 + 5;

struct node
{
    int v, e;
    node(int vv = 0, int ee = 0) : v(vv), e(ee) {}
};

vector <node> graph[maxn];
int dfsTime, dis[maxn], low[maxn];
bool isBridge[maxn], vis[maxn];
int totalBridge;

void findBridge(int u, int p = -1)
{
    vis[u] = 1;
    dis[u] = low[u] = dfsTime++;
    for (auto &it : graph[u])
    {
        int v = it.v;
        int e = it.e;
        if (v == p)
            continue;
        if (!vis[v])
        {
            findBridge(v, u);
            low[u] = min(low[u], low[v]);
            if (dis[u] < low[v])
            {
                isBridge[e] = 1;
                totalBridge++;
            }
        }
        else
        {
            low[u] = min(low[u], dis[v]);
        }
    }
}

int compo;
bool used[maxn];
vector <int> tree[maxn];


void bridgeTree(int src)
{
    used[src] = 1;
    int cur_compo = compo;
    queue <int> PQ;
    PQ.push(src);
    while(!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        for (auto &it : graph[u])
        {
            int v = it.v;
            int e = it.e;
            if (used[v])
                continue;
            if (isBridge[e])
            {
                compo++;
                tree[cur_compo].push_back(compo);
                tree[compo].push_back(cur_compo);
                bridgeTree(v);
            }
            else
            {
                PQ.push(v);
                used[v] = 1;
            }
        }
    }
}
int maxDis, maxDisNode;

void dfs(int u, int p, int d)
{
    if (d > maxDis)
    {
        maxDis = d;
        maxDisNode = u;
    }
    for (int v : tree[u])
    {
        if (v == u)
            continue;
        dfs(v, u, d+1);
    }
}

void init()
{
    dfsTime = 0;
    totalBridge = 0;
    compo = 1;
    for (int i = 0; i < maxn; i++)
    {
        vis[i] = 0;
        used[i] = 0;
        dis[i] = 0;
        low[i] = 0;
        isBridge[i] = 0;
        graph[i].clear();
        tree[i].clear();
    }
}

int main()
{
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        init();
        int n, m;
        cin >> n >> m;
        int src = n;
        for (int e = 1; e <= m; e++)
        {
             int u, v;
             cin >> u >> v;
             graph[u].push_back(v);
             graph[v].push_back(u);
             src = min(src, min(u, v));
        }
        findBridge(src);
        bridgeTree(src);
        maxDis = -1;
        maxDisNode = -1;
        dfs(1, -1, 0);
        maxDis = -1;
        dfs(maxDisNode, -1, 0);
        cout << (totalBridge � maxDis) << endl;
    }
}