题目描述

给定一个 $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$。给出的图无重边、无自环，且至少存在一种删边方案使得图仍然连通。

输出格式

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

4
4 6
1 2
1 3
1 4
2 3
2 4
3 4
4 5
1 2
2 3
3 4
1 4
1 3
5 6
1 3
2 3
1 4
2 4
1 5
2 5
5 7
1 2
2 3
3 4
4 5
1 5
2 5
1 4

4 15
4 4
6 12
4 4