# 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)

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

*are there where*

**(u, v)***and*

**u < v***.*

**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 ≤ 501 ≤ n ≤ 10

^{5}

n-1 ≤ m ≤ 7×10

^{5}

1 ≤ u, v ≤ n

Σn

_{i}≤ 5×10

^{5}

Σm

_{i}≤ 10

^{6}

### Output

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

### Samples

Input | Output |
---|---|

2 3 3 1 2 1 3 3 2 3 2 1 2 2 3 | Case 1: 3 Case 2: 0 |

#### rumman13

→

Login to submit