#P18144. Lalo's Lawyer Lost

Lalo's Lawyer Lost

Lalo's Lawyer Lost

Jesus, it's always the desert.

——James McGill, Better Call Saul

在帮 Lalo 交保释金时,Saul 和 Mike 在沙漠里迷路了。在沙漠中,他们发现了一株仙人掌:一个 nn 个点的连通无向图,满足每条边至多出现在一个简单环中。

已知 nn 是偶数。出于某种原因,Mike 和 Saul 想要解决下面这个问题:

定义 d(u,v)d(u,v) 为仙人掌中节点 uu 与 vv 之间的最短距离。把全部 nn 个节点划分成 n/2n/2 个点对 (ui,vi)(u_i,v_i),使每个节点恰好出现在一个点对中,并最大化

∑id(ui,vi).\sum_i d(u_i,v_i).

请求出这个最大值。

输入格式

第一行一个整数 tt(1≤t≤1051\le t\le 10^5),表示测试组数。

每组测试:

  • 第一行两个整数 n,mn,m(2≤n≤2⋅1052\le n\le 2\cdot 10^5,n−1≤m≤4⋅105n-1\le m\le 4\cdot 10^5,nn 为偶数);
  • 接下来 mm 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i),表示一条边。

保证这些边构成一株仙人掌。所有测试的 nn 之和不超过 2⋅1052\cdot 10^5,mm 之和不超过 4⋅1054\cdot 10^5。

输出格式

对每组测试输出一个整数,表示最大的距离和。

样例

输入:

3
4 3
1 2
2 3
3 4
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 8
8 3

输出:

4
7
11