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 .
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 ≤ 501 ≤ n ≤ 105n-1 ≤ m ≤ 7×1051 ≤ u, v ≤ nΣni ≤ 5×105Σmi ≤ 106
For each test case, print the case number and the result for that case.
2 3 3 1 2 1 3 3 2 3 2 1 2 2 3
Case 1: 3 Case 2: 0
0% Solution Ratio
Login to submit