Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

MaxFlow (II)

Limits: 5s, 1.0 GB

Given a connected undirected graph with n nodes and m edges and the capacity of each edge is 1. maxFlow(u, v) defines the maximum flow from node u to node v. You have to find out how many pair of nodes (u, v) are there where u < v and maxFlow(u, v) = 2 .

Input

The first line of the input contains an integer T , denoting the number of test cases. For each test case, the first line will have two integers n and m, denoting the number of nodes and edges of the graph. The following m lines will contain two integers u and v, denoting an undirected edge between u and v. You can assume that the graph won’t have any self loop.

Constraints:

1 ≤ T ≤ 50
1 ≤ n ≤ 105
n-1 ≤ m ≤ 7×105
1 ≤ u, v ≤ n
Σni ≤ 5×105
Σmi ≤ 106

Output

For each test case, print the case number and the result for that case.

Samples

InputOutput
2
3 3
1 2
1 3
3 2
3 2
1 2
2 3
Case 1: 3
Case 2: 0

Author
Discussion
Submit

Login to submit