간선 이사

$N$개의 정점으로 이루어진 트리 $T$가 주어진다. 정점에는 $1,2,\ldots,N$의 번호가 붙어 있다.

다음 연산을 정확히 한 번 수행하여 새로운 트리 $T'$를 만든다.

• $T$의 간선 하나를 삭제한다.
• 삭제 후 서로 다른 연결 컴포넌트에 속한 두 정점을 잇는 간선 하나를 추가한다.
• 추가한 간선은 삭제한 간선과 달라야 한다.

트리 $S$에서 두 정점 $u,v$ 사이의 거리를 $\operatorname{dist}_S(u,v)$로 나타내자. 다음 조건을 만족하는 정점 순서 없는 쌍 $\{u,v\}$의 개수를 $T$와 $T'$의 변화량이라고 한다.

가능한 모든 연산 중 변화량의 최솟값을 구하여라.

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

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

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

$N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$

각 $i$에 대해 $u_i$번 정점과 $v_i$번 정점을 잇는 간선이 존재한다.

각 테스트 케이스마다 변화량의 최솟값을 한 줄에 출력한다.

• $1\le T\le100$.
• $3\le N\le200\,000$.
• $1\le u_i,v_i\le N$ ($1\le i\le N-1$).
• 주어진 그래프는 트리이다.
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.