# Strongly connected

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

## Description

Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the graph is still a simple directed graph. Also, after you add these edges, this graph must NOT be strongly connected.
A simple directed graph is a directed graph having no multiple edges or graph loops.
A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.

## Input

The first line of date is an integer T, which is the number of the text cases.
Then T cases follow, each case starts of two numbers N and M, 1<=N<=100000, 1<=M<=100000, representing the number of nodes and the number of edges, then M lines follow. Each line contains two integers x and y, means that there is a edge from x to y.

## Output

For each case, you should output the maximum number of the edges you can add.
If the original graph is strongly connected, just output -1.

## Sample Input

3
3 3
1 2
2 3
3 1
3 3
1 2
2 3
1 3
6 6
1 2
2 3
3 1
4 5
5 6
6 4

## Sample Output

Case 1: -1
Case 2: 1
Case 3: 15

zhuyuanchen520

## Source

2013 Multi-University Training Contest 4