给定一个含有 $n$ 个顶点和 $m$ 条边的简单无向连通图 $G$，你需要选择两条不同的边进行删除，得到一个新图 $G'$，使得 $G'$ 仍然保持连通。

设删除的两条边分别为 $(p, q)$ 和 $(u, v)$。你需要最小化 $G'$ 中 $p$ 与 $q$ 之间的最短路径长度加上 $G'$ 中 $u$ 与 $v$ 之间的最短路径长度之和。输出该最小值以及达到该最小值的删除方案数。

输入格式

本题有多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $n, m$。
• 接下来的 $m$ 行，每行包含两个整数 $u, v$，表示一条边。

图中无重边和自环。保证至少存在一种删除方案使得图保持连通。

$1 \le T \le 5000, 1 \le \sum n, \sum m \le 5000, 4 \le n, 5 \le m$。

输出格式

对于每组测试数据：

输出一行，包含两个整数，分别表示最小值和方案数。

样例

输入样例 1

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

输出样例 1

4 15
4 4
6 12
4 4