P16918 [JLCPC 2026] Graph

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.

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.

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.

Translated by ChatGPT 5