All Falls Somewhere

Alice와 Bob은 그래프에서 말을 옮기는 게임 All Falls Somewhere를 한다. 게임판은 $N$개의 정점과 $M$개의 무방향 간선으로 이루어진 연결 그래프이다. 정점에는 $1$부터 $N$까지 번호가 붙어 있으며, 처음에는 각 정점에 말이 하나씩 놓여 있다.

먼저 Alice가 자신의 정점 $a$를 고르고, 그다음 Bob이 자신의 정점 $b$를 고른다. 두 정점은 서로 달라야 한다.

이후 게임은 $N$개의 턴 동안 진행된다. 홀수 번째 턴에는 Alice가, 짝수 번째 턴에는 Bob이 행동한다. $i$번째 턴에 행동하는 사람은 정점 $i$와 인접한 정점 하나를 고른 뒤, 정점 $i$에 있는 모든 말을 고른 정점으로 옮긴다.

모든 턴이 끝난 뒤 Alice의 점수는 정점 $a$에 있는 말의 수이고, Bob의 점수는 정점 $b$에 있는 말의 수이다. Alice는 Alice의 점수에서 Bob의 점수를 뺀 값을 최대화하고, Bob은 이 값을 최소화하도록 행동한다.

두 사람이 최적으로 행동할 때 Alice의 점수가 Bob의 점수보다 커지는 서로 다른 정점의 순서 있는 쌍 $(a,b)$의 개수를 구하여라.

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

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

각 테스트 케이스마다 조건을 만족하는 순서 있는 쌍 $(a,b)$의 개수를 한 줄에 출력한다.

• $1\leq T\leq1\,000$.
• $2\leq N\leq5\,000$.
• $N-1\le$.