#include<bits/stdc++.h>
using namespace std;

#define sc( x ) scanf( "%d" , &x )
#define REP( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( t , val ) memset( t , val , sizeof( t ) )

#define pb push_back
#define all( v ) v.begin() , v.end()
#define SZ( v ) ((int)(v).size())

#define fi first
#define se second
#define mp make_pair

#define N 25
#define INF (1<<29)

typedef pair< int , int > pii;
typedef vector< int > vi;
typedef vector< pii > vpii;

vi G[ N + 5 ] ;
int dist[ N + 5 ][ N + 5 ] , prev[ N + 5 ][ N + 5 ] , orig[ N + 5 ] , dest[ N + 5 ];

void add( int u , int v ){
    G[ u ].pb( v );
    G[ v ].pb( u );
}

int bfs( int n , int s , int &dd ){
    queue< int >Q;
    vi d( n , INF );
    d[ s ] = 0;
    Q.push( s );
    int u;

    while( !Q.empty() ){
        u = Q.front();
        Q.pop();
        REP( i , SZ( G[ u ] ) ){
            int v = G[ u ][ i ] ;
            if( d[ v ] >= INF ){
                d[ v ] = d[ u ] + 1;
                Q.push( v );
            }
        }
    }
    dd = d[ u ];
    return u;
}

int getDiam( int n ){
    int diam;
    int a = bfs( n , 0 , diam );
    bfs( n , a , diam );
    return diam;
}
int main(){
    int cases;
    sc( cases );
    REP( tc , cases ){
        int n , m;
        sc( n ) , sc( m );
        REP( i , n ) REP( j , n ) dist[ i ][ j ] = INF , prev[ i ][ j ] = -1;
        REP( i , n ) dist[ i ][ i ] = 0;
        REP( i , m ){
            int u , v;
            sc( u ) , sc( v );
            dist[ u ][ v ] = dist[ v ][ u ] = 1;
            prev[ u ][ v ] = u;
            prev[ v ][ u ] = v;
            orig[ i ] = u;
            dest[ i ] = v;
        }
        REP( k , n ) REP( i , n ) REP( j , n ) {
            if( dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] ) {
                dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ];
                prev[ i ][ j ] = prev[ k ][ j ];
            }
        }
        int ans = INF;
        REP( i , n ){
            REP( j , n ) G[ j ].clear() ;
            REP( j , n ) if( j != i ){
                add( prev[ i ][ j ] , j );
            }
            ans = min( ans , getDiam( n ) );
        }

        REP( i , m ){
            REP( j , n ) G[ j ].clear() ;
            int u = orig[ i ] , v = dest[ i ];
            add( u , v );
            REP( j , n ) {
                if( j == u ) continue;
                if( j == v ) continue;
                if( dist[ u ][ j ] < dist[ v ][ j ] ) add( prev[ u ][ j ] , j );
                else add( prev[ v ][ j ] , j );
            }
            ans = min( ans , getDiam( n ) );
        }

        printf( "Case #%d:\n" , tc + 1 );
        printf( "%d\n" , ans );
        puts( "" );
    }
}