트리 게임

트리에서 두 플레이어 $A$와 $B$가 아래의 규칙대로 게임을 하려고 한다.

$A$는 정점 $i$에 있고, $B$는 정점 $j$에 있다.

$A$와 $B$는 차례대로 아래의 행동을 반복한다.

• $A$는 현재 위치로부터 거리가 $1$인 정점 중 하나로 움직인다.
• $B$는 현재 위치로부터 거리가 $2$인 정점 중 하나로 움직인다.

이때 가만히 있을 수 없고 반드시 움직여야 한다.

만약 상대방이 있는 위치로 움직였다면, 상대방을 잡게 되어 움직인 플레이어가 게임에서 승리한다.

만약 $B$가 $10^{100}$번 움직일 때까지도 승부가 나지 않는다면 무승부가 된다.

두 플레이어는 매우 똑똑하므로 항상 최선으로 행동한다.

모든 시작 위치 쌍 $(i, j)$ $(1\leq i, j\leq N; i ≠ j)$ 에서 게임을 진행할 때, 플레이어 가 이기는 횟수를 구해보자.

트리의 정점의 개수를 의미하는 정수 $N$이 주어진다. $(4\leq N\leq 200\, 000)$

이어지는 $N-1$개의 줄에, 간선으로 연결된 두 정점을 의미하는 정수 $$가 공백으로 구분되어 주어진다.

모든 서로 다른 시작 위치에서 게임을 진행할 때, 플레이어 $A$가 이기는 횟수를 출력한다.