All Falls Down

Alice와 Bob은 두 말을 아래로 떨어뜨리는 게임 All Falls Down을 한다. 게임판은 $1$번 정점을 루트로 하는 트리이며, 각 자식 정점은 부모 정점보다 아래에 있다.

먼저 Alice가 서로 다른 두 정점 $u,v$를 고르고, 각 정점에 말 하나를 놓는다.

이후 Bob부터 시작하여 두 사람이 번갈아 턴을 진행한다. 자신의 턴에는 각 말이 놓인 정점의 자식을 하나씩 골라 두 말을 동시에 그 자식으로 이동해야 한다. 즉, 두 말을 모두 한 단계 아래로 떨어뜨려야 한다. 두 말 중 하나라도 더 내려갈 수 없다면 그 턴의 사람이 패배한다.

두 사람은 최적으로 행동한다. Alice가 이기는 서로 다른 정점의 순서 없는 쌍 $\{u,v\}$의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_{N-1}\ b_{N-1}$

이는 각 $i$에 대해 $a_i$번 정점과 $b_i$번 정점을 잇는 간선이 있음을 의미한다.

각 케이스마다 Alice가 이기는 정점 쌍의 개수를 한 줄에 출력한다.

• $1\leq T\leq200\,000$.
• $1\leq N\leq200\,000$.
• $1\leq a_i,b_i\leq N$ ($1\leq i\leq N-1$).
• 주어진 간선은 트리를 이룬다.
• 모든 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.