P16918 [JLCPC 2026] 图

给定一个 $n$ 个点 $m$ 条边的简单无向连通图 $G$。你需要选择两条不同的边删去，得到新图 $G'$，要求 $G'$ 仍然连通。 令删掉的两条边为 $(p,q)$ 和 $(u,v)$。你需要最小化 $p$ 到 $q$ 在 $G'$ 上的最短路长度与 $u$ 到 $v$ 在 $G'$ 上的最短路长度之和，输出这个最小值，并求出有多少种无序删边方案可以达到这个最小值。

第一行有一个整数 $T$（$1 \le T \le 5000$），表示数据组数。接下来 $T$ 段，每段描述一组数据。对于每组数据： - 第一行包含两个整数 $n, m$（$4 \le n \le 5000$，$5 \le m \le 5000$）。 - 接下来 $m$ 行，每行包含两个整数 $u, v$，表示一条边。 数据保证 $\sum n, \sum m \le 5000$。给出的图无重边、无自环，且至少存在一种删边方案使得图仍然连通。

对于每组数据，输出一行包含两个整数，分别表示最小值和达到最小值的无序删边方案数。