Uberfication

Salem decided to launch a new carpooling service that connects drivers with empty seats to people travelling the same way. Riders pay small amounts of money compared to other means of transportation, and drivers earn money without wasting time. The ride fee depends mainly on the distance between the trip starting point and the destination. To beat competitors in the same market, Salem decided to make the service free of charge between any two points that have more than one path to reach one another. For simplicity, we can assume that the city where he will launch his service is modeled as an undirected graph with N nodes and M edges. All edges have the same length of 1 unit. A path is a sequence of edges connecting a sequence of nodes that are all distinct from one another. Salem wants your help to give primary estimates for the revenue of his service by calculating the distance between all pairs of nodes that have a unique way to reach one another and ignoring all pairs that have more than one way between each other. In your revenue analysis, you must count each pair only once.

Your program will be tested on one or more test cases. The first line of the input contains a single integer T, the number of test cases (1 ≤ T ≤ 50). T test cases follow. The first line of each test case contains two integers N (1 ≤ N ≤ 50, 000) and M (0 ≤ M ≤ 150, 000), the number of nodes and edges in the city, separated by a single space. Each of the following M lines contains a pair of integers x and y (1 ≤ x, y ≤ N), separated by a single space, meaning that node x is connected to node y. The input is guaranteed to contain no more than one edge between any two nodes and no edge from a node to itself.

For each test case, print a single line containing an integer that is the total distance between all pairs of nodes having a unique way to reach one another.