간선 이사

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

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

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

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

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

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

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

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

• $1\le T\le100$.
• $3\le N\le200\,000$.
• $1\le u_i,v_i\le$ ().