#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > g;
vector<int> time_in,time_out,hieght;
int n,timee,flag;
void make_graph()
{
    g.clear();
    g.resize(n);
    time_in.clear();
    time_in.resize(n+1,-1);
    time_out.clear();
    time_out.resize(n+1,-1);
    hieght.clear();
    hieght.resize(n+1,0);
    timee=0;
    flag=0;
    int i,r,u,v;
    cin>>r;
    for(i=1;i<=r;i++)
    {
        cin>>u>>v;
        g[u].push_back(v);
    }
}


int topological_Sort_Util(int v, stack<int> &Stack)
{
    int i,ans=0;
    time_in[v]=++timee;
    for (i = 0; i < g[v].size(); ++i)
        {
            int curr;
            if (time_in[g[v][i]]<0)
            {
                curr=topological_Sort_Util(g[v][i], Stack);
            }
            else
            {
                if(time_out[g[v][i]]>0)
                {
                    curr=hieght[g[v][i]];
                }
                else
                {
                    flag=-1;
                    break;
                }
            }
             if(ans<curr)ans=curr;
        }
        if(flag==-1)
            return -1;
        ans++;
        time_out[v]=++timee;
        hieght[v]=ans;
    // Push current vertex to stack which stores result
    Stack.push(v);
    return ans;
}

void topological_Sort()
{
    stack<int> Stack;

    for (int i = 0; i < n; i++)
      if (time_in[i] < 0)
        topological_Sort_Util(i, Stack);

    while (Stack.empty() == false && flag!=-1)
    {
        //cout << Stack.top() << " ";
        Stack.pop();
    }
}
int main()
{
    int t,x;
    cin>>t;
    for(x=1;x<=t;x++)
    {
        cin>>n;
        make_graph();
        topological_Sort();
        int i,ans=0;
        for(i=0;i<n;i++)
            if(hieght[i]>ans)ans=hieght[i];

        if(flag==-1)
        {
            cout<<"Case "<<x<<": Never Ends\n";
        }
        else
        {
            cout<<"Case "<<x<<": "<<ans<<" semester(s)\n";
        }
    }
    return 0;
}