우버화

Salem은 빈 좌석이 있는 운전자와 같은 방향으로 이동하는 사람을 연결하는 새로운 카풀 서비스를 시작하기로 했다. 이용자는 다른 교통수단보다 적은 요금을 내고, 운전자는 시간을 낭비하지 않고 돈을 벌 수 있다. 요금은 주로 출발지와 목적지 사이의 거리에 따라 결정된다. 같은 시장의 경쟁자를 이기기 위해 Salem은 두 지점 사이에 서로 도달하는 경로가 두 개 이상이면 그 구간의 서비스를 무료로 제공하기로 했다. 단순화를 위해 서비스를 시작할 도시는 N개의 노드와 M개의 간선으로 이루어진 무방향 그래프로 모델링한다. 모든 간선의 길이는 1이다. 경로는 서로 다른 노드들을 잇는 간선의 나열이다. Salem은 서로 도달하는 방법이 하나뿐인 모든 노드 쌍 사이의 거리를 계산하고, 서로 도달하는 방법이 두 개 이상인 모든 쌍은 무시하여 서비스 수익의 기초 추정치를 얻고자 한다. 수익 분석에서는 각 쌍을 한 번만 센다.

프로그램은 하나 이상의 테스트 케이스에 대해 실행된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 50). 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 노드 수 N (1 ≤ N ≤ 50, 000)과 간선 수 M (0 ≤ M ≤ 150, 000)이 공백 하나를 사이에 두고 주어진다. 다음 M개 줄에는 각각 두 정수 x와 y (1 ≤ x, y ≤ N)가 공백 하나를 사이에 두고 주어지며, 노드 x와 노드 y가 연결되어 있음을 뜻한다. 입력에는 두 노드 사이에 간선이 두 개 이상 있거나 자기 자신으로 가는 간선이 없다.

각 테스트 케이스마다 서로 도달하는 방법이 하나뿐인 모든 노드 쌍 사이의 거리의 합을 나타내는 정수를 한 줄에 출력한다.