Troykalar#9109
Ağac, yəni dövrü olmayan əlaqəli istiqamətsiz qraf verilib. Hər hansı iki və zirvələri üçün d(x, y) ilə və arasındakı yeganə sadə yolun uzunluğunu (yəni kənarların sayını) ifadə edək. Bütün (sıralanmamış) \{x, y, z\} troykalarını sayın ki, d(x, y) = d(y, z) = d(z, x) > 0.
Birinci sətir testlərin sayı olan z~(1 \le z \le 20) sayını ehtiva edir. Daha sonra testlərin təsvirləri verilir.
Hər testin birinci sətiri təklikdə bir ədəd ehtiva edir — zirvələrin sayı n~(3 \le n \le 10^5). Növbəti n - 1 sətirin hər biri iki tam ədəd və b~(1 \le a, b \le n) ehtiva edir və bunlar və zirvələri arasında kənarı ifadə edir.
Hər test üçün bir tam ədəd çıxarın — tapılmış troykaların sayı.
Nümunə 1