1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int MAXN=100010;
  8 
  9 struct Edge{
 10     int to,next;
 11 }edges[MAXN];
 12 
 13 int head[MAXN],tot;
 14 
 15 void init(){
 16     memset(head,-1,sizeof(head));
 17     tot=0;
 18 }
 19 
 20 void addEdge(int u,int v){
 21     edges[tot].to=v;
 22     edges[tot].next=head[u];
 23     head[u]=tot++;
 24 }
 25 
 26 int DFN[MAXN],LOW[MAXN],Stack[MAXN],NUM[MAXN],Belong[MAXN];
 27 bool Instack[MAXN];
 28 int scc,Index,top;
 29 
 30 void Tarjan(int u){
 31     DFN[u]=LOW[u]=++Index;
 32     Stack[top++]=u;
 33     Instack[u]=true;
 34 
 35     int v;
 36     for(int i=head[u];i!=-1;i=edges[i].next){
 37          v=edges[i].to;
 38 
 39         if(!DFN[v]){
 40             Tarjan(v);
 41             if(LOW[u]>LOW[v])
 42                 LOW[u]=LOW[v];
 43         }else if(Instack[v]&&LOW[u]>DFN[v]) LOW[u]=DFN[v];
 44     }
 45 
 46     if(LOW[u]==DFN[u]){
 47         scc++;
 48         do{
 49             v=Stack[--top];
 50             NUM[scc]++;
 51             Instack[v]=false;
 52             Belong[v]=scc;
 53         }while(v!=u);
 54     }
 55 }
 56 
 57 int in[MAXN],out[MAXN];
 58 void solve(long long n,long long m){
 59     memset(DFN,0,sizeof(DFN));
 60     memset(NUM,0,sizeof(NUM));
 61     memset(Instack,0,sizeof(Instack));
 62     top=Index=scc=0;
 63 
 64     for(int i=1;i<=n;i++)
 65         if(!DFN[i])
 66             Tarjan(i);
 67 
 68     if(scc==1){
 69         cout<<-1<<endl;
 70         return;
 71     }
 72 
 73     memset(in,0,sizeof(in));
 74     memset(out,0,sizeof(out));
 75 
 76     for(int i=1;i<=n;i++)
 77     for(int j=head[i];j!=-1;j=edges[j].next){
 78         int v=edges[j].to;
 79         if(Belong[i]!=Belong[v]){
 80             out[Belong[i]]++;
 81             in[Belong[v]]++;
 82         }
 83     }
 84 
 85     long long ans=0;
 86 
 87     for(int i=1;i<=scc;i++){
 88         if(in[i]==0||out[i]==0){
 89             ans=max(ans,(n*n-(n-NUM[i])*NUM[i]-n-m));
 90         }
 91     }
 92 
 93     //注意数据溢出的情况
 94 
 95     printf("%lld\n",ans);
 96 }
 97 
 98 
 99 int main(){
100     int T;
101     scanf("%d",&T);
102     for(int i=1;i<=T;i++){
103 
104         init();
105         int n,m;
106         scanf("%d%d",&n,&m);
107         for(int j=0;j<m;j++){
108             int u,v;
109             scanf("%d%d",&u,&v);
110             addEdge(u,v);
111         }
112         printf("Case %d: ",i);
113         solve(n,m);
114 
115     }
116 }