#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/stack:200000000")
#define ll long long int
#define inf ( int )( 1e9 + 1e9 )
#define mxs (int)( 1e6 + 10 )
#define md int mid = ( l + r )>>1;
#define mod 10000000000007//(ll)(1e9)+7
//int dx[]={+1,0,+0,-1};///Four Directions
//int dy[]={+0,-1,+1,+0};///Four directions
//int dx [] = {+1,-1,+0,+0,-1,-1,+1,+1};///Eight Directions
//int dy [] = {+0,+0,+1,-1,+1,-1,-1,+1};///Eight Directions
int t, n, m, j,a, b, c, d, e,f, i,ans,cases , pos , num , root;
string s, s2, s3, s4;
int visited [ 510 ] , level [ 510 ] , parent [ 510 ];
queue < int > qu;
vector < int > graph [ mxs ];
void brainfuck();
int finder( int node );
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
brainfuck();
return 0;
}
void brainfuck()
{
cin>>t;
while( t-- )
{
cin>>n>>m;
for ( i = 0 ; i <= n; i++ )
{
graph [ i ].clear();
}
while( m-- )
{
cin>>a>>b;
graph [ a ].push_back( b );
graph [ b ].push_back( a );
}
ans = inf;
for ( i = 0; i < n; i++ )
{
ans = min( ans , finder( i ) );
}
cout<<"Case "<<++cases<<": ";
if ( ans == inf )cout<<"impossible\n";
else cout<<ans<<"\n";
}
}
int finder( int node )
{
int lol = inf;
while( !qu.empty() )qu.pop();
memset( visited , 0 , sizeof visited );
memset( parent , -1, sizeof parent );
level [ node ] = 0;
qu.push( node );
visited [ node ] = 1;
while( !qu.empty() )
{
a = qu.front();
qu.pop();
int sz = graph [ a ].size();
for ( j = 0 ; j < sz; j++ )
{
b = graph [ a ] [ j ];
if ( !visited [ b ] )
{
parent [ b ] = a;
qu.push( b );
level [ b ] = level [ a ] + 1;
visited [ b ] = 1;
}
else if ( parent [ a ] != b )
{
lol = min( lol , level [ a ] + level [ b ] + 1 );
//return ( level [ a ] + level [ b ] + 1);
}
}
}
return lol;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9zdGFjazoyMDAwMDAwMDAiKQojZGVmaW5lIGxsIGxvbmcgbG9uZyBpbnQKI2RlZmluZSBpbmYgKCBpbnQgKSggMWU5ICsgMWU5ICkKI2RlZmluZSBteHMgKGludCkoIDFlNiArIDEwICkKI2RlZmluZSBtZCAgaW50IG1pZCA9ICggbCArIHIgKT4+MTsKI2RlZmluZSBtb2QgMTAwMDAwMDAwMDAwMDcvLyhsbCkoMWU5KSs3Ci8vaW50IGR4W109eysxLDAsKzAsLTF9Oy8vL0ZvdXIgRGlyZWN0aW9ucwovL2ludCBkeVtdPXsrMCwtMSwrMSwrMH07Ly8vRm91ciBkaXJlY3Rpb25zCi8vaW50IGR4IFtdID0geysxLC0xLCswLCswLC0xLC0xLCsxLCsxfTsvLy9FaWdodCBEaXJlY3Rpb25zCi8vaW50IGR5IFtdID0geyswLCswLCsxLC0xLCsxLC0xLC0xLCsxfTsvLy9FaWdodCBEaXJlY3Rpb25zCmludCB0LCBuLCBtLCBqLGEsIGIsIGMsIGQsIGUsZiwgaSxhbnMsY2FzZXMgLCBwb3MgLCBudW0gLCByb290OwpzdHJpbmcgcywgczIsIHMzLCBzNDsKaW50IHZpc2l0ZWQgWyA1MTAgXSAsIGxldmVsIFsgNTEwIF0gLCBwYXJlbnQgWyA1MTAgXTsKcXVldWUgPCBpbnQgPiBxdTsKdmVjdG9yIDwgaW50ID4gZ3JhcGggWyBteHMgXTsKdm9pZCBicmFpbmZ1Y2soKTsKaW50IGZpbmRlciggaW50IG5vZGUgKTsKaW50IG1haW4oKQp7CiAgICAvL2ZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTsKICAgIC8vZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKICAgIGJyYWluZnVjaygpOwogICAgcmV0dXJuIDA7Cn0Kdm9pZCBicmFpbmZ1Y2soKQp7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSggdC0tICkKICAgIHsKICAgICAgICBjaW4+Pm4+Pm07CiAgICAgICAgZm9yICggaSA9IDAgOyBpIDw9IG47IGkrKyApCiAgICAgICAgewogICAgICAgICAgICBncmFwaCBbIGkgXS5jbGVhcigpOwogICAgICAgIH0KICAgICAgICB3aGlsZSggbS0tICkKICAgICAgICB7CiAgICAgICAgICAgIGNpbj4+YT4+YjsKICAgICAgICAgICAgZ3JhcGggWyBhIF0ucHVzaF9iYWNrKCBiICk7CiAgICAgICAgICAgIGdyYXBoIFsgYiBdLnB1c2hfYmFjayggYSApOwogICAgICAgIH0KICAgICAgICBhbnMgPSBpbmY7CiAgICAgICAgZm9yICggaSA9IDA7IGkgPCBuOyBpKysgKQogICAgICAgIHsKICAgICAgICAgICAgYW5zID0gbWluKCBhbnMgLCBmaW5kZXIoIGkgKSApOwogICAgICAgIH0KICAgICAgICBjb3V0PDwiQ2FzZSAiPDwrK2Nhc2VzPDwiOiAiOwogICAgICAgIGlmICggYW5zID09IGluZiApY291dDw8ImltcG9zc2libGVcbiI7CiAgICAgICAgZWxzZSBjb3V0PDxhbnM8PCJcbiI7CiAgICB9Cn0KaW50IGZpbmRlciggaW50IG5vZGUgKQp7CiAgICBpbnQgbG9sID0gaW5mOwogICAgd2hpbGUoICFxdS5lbXB0eSgpIClxdS5wb3AoKTsKICAgIG1lbXNldCggdmlzaXRlZCAsIDAgLCBzaXplb2YgdmlzaXRlZCApOwogICAgbWVtc2V0KCBwYXJlbnQgLCAtMSwgc2l6ZW9mIHBhcmVudCApOwogICAgbGV2ZWwgWyBub2RlIF0gPSAwOwogICAgcXUucHVzaCggbm9kZSApOwogICAgdmlzaXRlZCBbIG5vZGUgXSA9IDE7CiAgICB3aGlsZSggIXF1LmVtcHR5KCkgKQogICAgewogICAgICAgIGEgPSBxdS5mcm9udCgpOwogICAgICAgIHF1LnBvcCgpOwogICAgICAgIGludCBzeiA9IGdyYXBoIFsgYSBdLnNpemUoKTsKICAgICAgICBmb3IgKCBqID0gMCA7IGogPCBzejsgaisrICkKICAgICAgICB7CiAgICAgICAgICAgIGIgPSBncmFwaCBbIGEgXSBbIGogXTsKICAgICAgICAgICAgaWYgKCAhdmlzaXRlZCBbIGIgXSApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHBhcmVudCBbIGIgXSA9IGE7CiAgICAgICAgICAgICAgICBxdS5wdXNoKCBiICk7CiAgICAgICAgICAgICAgICBsZXZlbCBbIGIgXSA9IGxldmVsIFsgYSBdICsgMTsKICAgICAgICAgICAgICAgIHZpc2l0ZWQgWyBiIF0gPSAxOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYgKCBwYXJlbnQgWyBhIF0gIT0gYiApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxvbCA9IG1pbiggbG9sICwgbGV2ZWwgWyBhIF0gKyBsZXZlbCBbIGIgXSArIDEgKTsKICAgICAgICAgICAgICAgIC8vcmV0dXJuICggbGV2ZWwgWyBhIF0gKyBsZXZlbCBbIGIgXSArIDEpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGxvbDsKfQ==