#include <iostream>

 #include<cstring>

 #include<cstdio>

 #include<stdlib.h>

 #include<stack>

 using namespace std;

 #define N 100010

 #define M 100010

 #define INF 0xfffffff

 int a[][];

 stack<int>s;

 struct node

 {

     int u,v,next;

 }ed[M*];

 int scc,sccno[N],head[N],lowlink[N],pre[N],dep,num[N],x[M],y[M],din[N],dout[N],o;

 void init()

 {

     o = ;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v)

 {

     ed[o].u = u;

     ed[o].v = v;

     ed[o].next = head[u];

     head[u] = o++;

 }

 void dfs(int u)

 {

     int i;

     lowlink[u] = pre[u] = ++dep;

     s.push(u);

     for( i = head[u] ; i != - ; i = ed[i].next)

     {

         int v = ed[i].v;

         if(!pre[v])

         {

             dfs(v);

             lowlink[u] = min(lowlink[u],lowlink[v]);

         }

         else if(!sccno[v])

         lowlink[u] = min(lowlink[u],pre[v]);

     }

     if(lowlink[u]==pre[u])

     {

         scc++;

         for(;;)

         {

             int x = s.top();

             s.pop();

             sccno[x] = scc;

             if(x==u) break;

         }

     }

 }

 void find_scc(int n)

 {

     for(int i = ; i <= n ;i++)

     if(!pre[i])

     dfs(i);

 }

 int main()

 {

     int i,t,n,m,a,b,kk=;

     cin>>t;

     while(t--)

     {

         init();kk++;

         memset(num,,sizeof(num));

         memset(pre,,sizeof(pre));

         memset(din,,sizeof(din));

         memset(dout,,sizeof(dout));

         memset(sccno,,sizeof(sccno));

         scanf("%d%d",&n,&m);

         for(i = ; i <= m ; i++)

         {

             scanf("%d%d",&a,&b);

             x[i] = a;y[i] = b;

             add(a,b);

         }

         scc=;dep=;

         find_scc(n);

         printf("Case %d: ",kk);

         if(scc==)

         {

             cout<<"-1\n";

             continue;

         }

         for(i = ; i <= n ; i++)

         num[sccno[i]]++;

         for(i = ; i <= m ;i++)

         {

             if(sccno[x[i]]!=sccno[y[i]])

             {

                 dout[sccno[x[i]]]++;

                 din[sccno[y[i]]]++;

             }

         }

         long long minz = INF;

         for(i =  ;i <= scc ; i++)

         if(minz>num[i]&&(din[i]==||dout[i]==))

         minz = num[i];

         long long ss=;

         ss = minz*(minz-)+(n-minz)*(n-minz-)+minz*(n-minz);

         cout<<ss-m<<endl;

     }

     return ;

 }