ZJH and Monkeys
题号：NC15681
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.  

One day, zjh is wandering in the campus,and he finds a tree with n monkeys on it, and he labels the monkeys from 1 to n. A triple of monkeys (a,b,c) is called happy if and only if the absolute value of the difference of the distance from c to a the distance from c to b holds the same parity(奇偶性) as n. Now zjh wants to know how many triples of monkeys are happy.

输入描述:

There are multiple test cases. 
The first line of input contains an integer T, indicating the number of test cases. 
For each test case:
The first line contains an integer n
In the next n-1 lines, each line contains two integers ui and vi, denoting an edge between monkey ui and monkey v­i.

输出描述:

For each test case, output an integer S, denoting the number of triple of monkeys that are happy.
示例1

输入

复制 
1
3
1 2
2 3

输出

复制 
12

说明

The 12 triples are:
(1,2,1)
(1,2,2)
(1,2,3)
(2,1,1)
(2,1,2)
(2,1,3)
(2,3,1)
(2,3,2)
(2,3,3)
(3,2,1)
(3,2,2)
(3,2,3)