Fracture Ray

$N$개의 정점과 $M$개의 간선으로 이루어진 연결된 단순 무방향 그래프가 주어진다. 정점에는 $1$번부터 $N$번까지 번호가 붙어 있다.

서로 다른 간선 세 개를 골라 광선으로 부수려고 한다. 고른 세 간선은 다음 조건을 모두 만족해야 한다.

1. 고른 세 간선과 그 끝점만으로 이루어진 그래프가 연결되어 있다.
2. 원래 그래프에서 고른 세 간선을 모두 제거하면 그래프가 연결되어 있지 않게 된다.

광선은 간선만 제거하며 정점은 제거하지 않는다. 따라서 간선을 제거한 뒤 고립된 정점이 생긴 경우에도 그래프가 연결되어 있지 않은 것으로 본다.

조건을 만족하는 간선 집합의 개수를 구하여라. 같은 세 간선을 고르는 순서만 다른 경우는 같은 집합으로 센다.

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

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

각 테스트 케이스마다 조건을 만족하는 간선 집합의 개수를 출력한다.

• $1\leq T\leq100\,000$.
• $1\leq N\leq100\,000$.
• $0\le M\le$.