Moving an Edge

You are given a tree $T$ with $N$ vertices numbered $1,2,\ldots,N$.

Perform the following operation exactly once to obtain a new tree $T'$.

• Delete one edge of $T$.
• Add one edge whose endpoints belong to different connected components after the deletion.
• The added edge must be different from the deleted edge.

For a tree $S$, let $\operatorname{dist}_S(u,v)$ denote the distance between vertices $u$ and $v$. Define the amount of change between $T$ and $T'$ as the number of unordered vertex pairs $\{u,v\}$ satisfying

Find the minimum possible amount of change.

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

$N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$

For each $i$, there is an edge connecting vertices $u_i$ and $v_i$.

For each test case, print the minimum possible amount of change on one line.

• $1\le T\le100$.
• $3\le N\le200\,000$.
• $1\le u_i,v_i\le N$ ($1\le i\le N-1$).
• The given graph is a tree.
• The sum of $N$ over all test cases does not exceed $200\,000$.