The prison of Nlogonia has been recently remodeled. It has $$$n$$$ cells, each with the capacity for a single inmate. Some cells are connected to each other in such a way that it is possible to go from any cell to any other in a unique way (without revisiting cells). In other words, the graph of the cells and their connections is a tree. Three very dangerous inmates have arrived at the prison and need to be assigned to different cells with one restriction: no two of them can be in connected cells, as they could devise a plan to escape. Count the number of ways to select their 3 cells while satisfying the restriction.
Note: The permutations of cells count only once (1, 2, 3 and 2, 3, 1 are considered the same). Two ways are considered distinct if any of the cells is different.
Each case starts with an integer $$$t$$$, the number of cases. Each of the $$$t$$$ cases starts with an integer $$$n$$$, the number of cells in the prison. This is followed by $$$n-1$$$ lines, each with a pair of integers $$$u, v$$$ indicating that cells $$$u$$$ and $$$v$$$ are connected.
For each case, print a single integer, the number of ways to select the 3 cells while satisfying the restriction.
For all cases, it holds that $$$n \geq 3$$$, $$$0 \leq u, v \leq n-1$$$, and $$$t \leq 40$$$.
13 Points: $$$n \leq 20$$$
26 Points: $$$n \leq 300$$$
14 Points: $$$n \leq 2000$$$
11 Points: $$$n \leq 100000$$$ and the edges are of the form $$$(i, i+1)$$$, $$$0 \leq i \leq n-2$$$
6 Points: $$$n \leq 100000$$$ and the edges are of the form $$$(0, i)$$$, $$$1 \leq i \leq n-1$$$
30 Points: $$$n \leq 100000$$$
3 5 0 1 1 2 2 3 3 4 5 0 1 0 2 0 3 3 4 7 0 1 0 2 1 3 1 4 2 5 2 6
1 2 12
