#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 ] , orig[ N + 5 ] , dest[ N + 5 ];

int main(){
    int cases;
    sc( cases );
    REP( tc , cases ){
        int n , m;
        sc( n ) , sc( m );
        REP( i , N ) G[ i ].clear();
        REP( i , n ) REP( j , n ) dist[ i ][ j ] = INF;
        REP( i , n ) dist[ i ][ i ] = 0;
        REP( i , m ){
            int u , v;
            sc( u ) , sc( v );
            dist[ u ][ v ] = dist[ v ][ u ] = 2;
            orig[ i ] = u;
            dest[ i ] = v;
        }
        REP( k , n ) REP( i , n ) REP( j , n ) dist[ i ][ j ] = min( dist[ i ][ j ] , dist[ i ][ k ] + dist[ k ][ j ] );
        int ans = INF;
        REP( i , n ){
            vi vec;
            REP( j , n ) vec.pb( dist[ i ][ j ] );
            sort( all( vec ) );
            reverse( all( vec ) );
            if( SZ( vec ) >= 2 ) ans = min( ans , vec[ 0 ] + vec[ 1 ] );
        }
        REP( i , m ){
            int u = orig[ i ] , v = dest[ i ];
            vi vec;
            REP( w , n )
                if( u != w && v != w ) vec.pb( min( dist[ u ][ w ] , dist[ v ][ w ] ) + 1 );
            sort( all( vec ) );
            reverse( all( vec ) );

            if( SZ( vec ) >= 2 ){
                 ans = min( ans , vec[ 0 ] + vec[ 1 ] );
            }
        }
        printf( "Case #%d:\n" , tc + 1 );
        printf( "%d\n" , ans == INF ? 0 : (ans / 2) );
        puts( "" );
    }
}