Cube of a Graph

The cube $G^3$ of a graph $G = (V, E)$ is the graph on the vertex set $V$ in which two vertices are joined by an edge whenever their distance in $G$ is at most three. The distance between two vertices is the number of edges on a shortest path connecting them.

A bridge (also called a cut-edge) is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it lies on no cycle. The degree of a vertex is the number of edges incident to it, and a bridge is nontrivial when neither of its two endpoints has degree one.

Building on these ideas, three notions are defined.

• A vertex is a pure bridge vertex if every edge incident to it is a nontrivial bridge.
• Three distinct, mutually adjacent vertices, each of degree at least three, form a pure bridge triangle if every edge of $G$ that is incident to exactly one of the three vertices is a nontrivial bridge.
• Two adjacent vertices form a pure bridge pair if both of them are pure bridge vertices.

Figure 1. A connected graph with seven nontrivial bridges, drawn as dotted lines. It has three pure bridge vertices 7, 8, and 15, one pure bridge triangle $\{9, 10, 14\}$, and one pure bridge pair $\{7, 8\}$.

It is known that the cube of any connected graph is Hamiltonian-connected: every two vertices of $G^3$ are joined by a Hamiltonian path.

Given a connected graph, count all of its pure bridge vertices, pure bridge triangles, and pure bridge pairs.

The first line contains the number of test cases $T$. Each test case follows.

The first line of a test case contains two integers $n$ and $m$: the number of vertices and the number of edges of a graph $G$, where $n \le 3000$ and $m \le 1{,}000{,}000$. Each of the next $m$ lines contains two integers $u$ and $v$, describing an edge between vertices $u$ and $v$. The graph is connected and its vertex set is $\{1, 2, \dots, n\}$.

For each test case, print one line with three integers separated by single spaces: the number of pure bridge vertices, the number of pure bridge triangles, and the number of pure bridge pairs, in that order.