Fracture Ray

You are given a connected simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ through $N$.

Choose three distinct edges to destroy with a ray. The chosen edges must satisfy both conditions below.

1. The graph consisting only of the three chosen edges and their endpoints is connected.
2. Removing all three chosen edges from the original graph makes it disconnected.

The ray removes only edges, not vertices. In particular, a graph with an isolated vertex after the removal is considered disconnected.

Count the sets of three edges satisfying the conditions. Different orders of choosing the same three edges are counted only once.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the number of edge sets satisfying the conditions.

• $1\leq T\leq100\,000$.
• $1\leq N\leq100\,000$.
• $0\le M$.