题意：求最多可以加多少边，使得最新的图还不是强连通图。
分析：最终添加完边的图，肯定可以分成两个部X和Y，其中只有X到Y的边没有Y到X的边，那么要使得边数尽可能的多，则X部肯定是一个完全图，Y部也是，同时X部中每个点到Y部的每个点都有一条边，但Y没有可以到达X的点，设X有a个点，Y有b个点，a+b=n，那么新图总边数sum=（a-1）*a+（b-1）*b+a*b-m=n*n-n-m-a*b，显然a*b越小越好，且X和Y必定是入度为0或出度为0，否则也能进也能出肯定强连通了。
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N];
int n,m,step,scc,top,tot;
int head[N],dfn[N],low[N],belong[N],Stack[N];
int num[N],in[N],out[N];
bool instack[N];
void init()
{
tot=;top=;scc=;step=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(in,);FILL(out,);FILL(num,);
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
int v;
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
v=e[i].v;
if(!dfn[v])
{
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
}
else if(instack[v])
{
if(low[u]>dfn[v])low[u]=dfn[v];
}
}
if(dfn[u]==low[u])
{
scc++;
do
{
v=Stack[--top];
instack[v]=false;
belong[v]=scc;
num[scc]++;
}while(v!=u);
}
}
void solve()
{
for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i);
if(scc==)
{
puts("-1");
return;
}
for(int u=;u<=n;u++)
{
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(belong[u]!=belong[v])
{
out[belong[u]]++;
in[belong[v]]++;
}
}
}
LL sum=1LL*n*n-n-m,ans=;
for(int i=;i<=scc;i++)
{
if(!in[i]||!out[i])
ans=max(ans,sum-1LL*(n-num[i])*num[i]);
}
printf("%I64d\n",ans);
}
int main()
{
int T,u,v,cas=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
}
printf("Case %d: ",cas++);
solve();
}
}