H. Graph
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a simple undirected connected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, you need to choose two distinct edges to delete, obtaining a new graph $$$G'$$$, such that $$$G'$$$ remains connected.

Let the two deleted edges be $$$(p,q)$$$ and $$$(u,v)$$$. You need to minimize the sum of the shortest path between $$$p$$$ and $$$q$$$ in $$$G'$$$ plus the shortest path between $$$u$$$ and $$$v$$$ in $$$G'$$$. Output this minimum value and the number of deletion schemes that achieve it.

Input

This problem has multiple test cases.

The first line contains an integer $$$T$$$ — the number of test cases.

For each test case:

The first line contains two integers $$$n,m$$$.

The next $$$m$$$ lines each contain two integers $$$u,v$$$, representing an edge.

The graph has no multi-edges or self-loops. It is guaranteed that at least one deletion scheme exists such that the graph remains connected.

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

Output

For each test case:

Output a single line with two integers — the minimum value and the number of schemes.

Example
Input
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
Output
4 15
4 4
6 12
4 4