All Falls Somewhere

Alice and Bob play All Falls Somewhere on a connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and initially there is one piece on every vertex.

First, Alice chooses her vertex $a$. Then Bob chooses his vertex $b$. The two chosen vertices must be distinct.

The game consists of $N$ turns. Alice acts on odd-numbered turns, and Bob acts on even-numbered turns. On turn $i$, the active player chooses a vertex adjacent to vertex $i$ and moves every piece currently on vertex $i$ to the chosen vertex.

After all turns, Alice's score is the number of pieces on vertex $a$, and Bob's score is the number of pieces on vertex $b$. Alice maximizes Alice's score minus Bob's score, while Bob minimizes this value.

Count the ordered pairs of distinct vertices $(a,b)$ for which Alice's score is greater than Bob's score when both players play optimally.

The input is given in the following format:

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

For each test case, print the number of ordered pairs $(a,b)$ satisfying the condition.

• $1\leq T\leq1\,000$.
• $2\leq N\leq5\,000$.
• $N-1\le$.