Problem Description

Given a simple, undirected, connected graph $G$ with $n$ vertices and $m$ edges. You need to choose two different edges to delete, obtaining a new graph $G'$, and $G'$ must remain connected.

Let the two deleted edges be $(p,q)$ and $(u,v)$. You need to minimize the sum of the shortest path length from $p$ to $q$ in $G'$ and the shortest path length from $u$ to $v$ in $G'$. Output this minimum value, and also compute how many unordered edge-deletion plans can achieve this minimum.

Input Format

The first line contains an integer $T$ ($1 \le T \le 5000$), the number of test cases. Then follow $T$ blocks, each describing one test case. For each test case:

• The first line contains two integers $n, m$ ($4 \le n \le 5000$, $5 \le m \le 5000$).
• The next $m$ lines each contain two integers $u, v$, representing an edge.

The constraints guarantee that $\sum n, \sum m \le 5000$. The given graph has no multiple edges and no self-loops, and there exists at least one way to delete edges such that the graph remains connected.

Output Format

For each test case, output one line containing two integers: the minimum value, and the number of unordered edge-deletion plans that achieve this minimum.

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

Hint

Translated by ChatGPT 5