fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #pragma comment(linker, "/stack:200000000")
  4. #define ll long long int
  5. #define inf ( int )( 1e9 + 1e9 )
  6. #define mxs (int)( 1e6 + 10 )
  7. #define md int mid = ( l + r )>>1;
  8. #define mod 10000000000007//(ll)(1e9)+7
  9. //int dx[]={+1,0,+0,-1};///Four Directions
  10. //int dy[]={+0,-1,+1,+0};///Four directions
  11. //int dx [] = {+1,-1,+0,+0,-1,-1,+1,+1};///Eight Directions
  12. //int dy [] = {+0,+0,+1,-1,+1,-1,-1,+1};///Eight Directions
  13. int t, n, m, j,a, b, c, d, e,f, i,ans,cases , pos , num , root;
  14. string s, s2, s3, s4;
  15. int visited [ 510 ] , level [ 510 ] , parent [ 510 ];
  16. queue < int > qu;
  17. vector < int > graph [ mxs ];
  18. void brainfuck();
  19. int finder( int node );
  20. int main()
  21. {
  22. //freopen("input.txt","r",stdin);
  23. //freopen("output.txt","w",stdout);
  24. ios_base::sync_with_stdio(false);
  25. cin.tie(NULL);
  26. cout.tie(NULL);
  27. brainfuck();
  28. return 0;
  29. }
  30. void brainfuck()
  31. {
  32. cin>>t;
  33. while( t-- )
  34. {
  35. cin>>n>>m;
  36. for ( i = 0 ; i <= n; i++ )
  37. {
  38. graph [ i ].clear();
  39. }
  40. while( m-- )
  41. {
  42. cin>>a>>b;
  43. graph [ a ].push_back( b );
  44. graph [ b ].push_back( a );
  45. }
  46. ans = inf;
  47. for ( i = 0; i < n; i++ )
  48. {
  49. ans = min( ans , finder( i ) );
  50. }
  51. cout<<"Case "<<++cases<<": ";
  52. if ( ans == inf )cout<<"impossible\n";
  53. else cout<<ans<<"\n";
  54. }
  55. }
  56. int finder( int node )
  57. {
  58. int lol = inf;
  59. while( !qu.empty() )qu.pop();
  60. memset( visited , 0 , sizeof visited );
  61. memset( parent , -1, sizeof parent );
  62. level [ node ] = 0;
  63. qu.push( node );
  64. visited [ node ] = 1;
  65. while( !qu.empty() )
  66. {
  67. a = qu.front();
  68. qu.pop();
  69. int sz = graph [ a ].size();
  70. for ( j = 0 ; j < sz; j++ )
  71. {
  72. b = graph [ a ] [ j ];
  73. if ( !visited [ b ] )
  74. {
  75. parent [ b ] = a;
  76. qu.push( b );
  77. level [ b ] = level [ a ] + 1;
  78. visited [ b ] = 1;
  79. }
  80. else if ( parent [ a ] != b )
  81. {
  82. lol = min( lol , level [ a ] + level [ b ] + 1 );
  83. //return ( level [ a ] + level [ b ] + 1);
  84. }
  85. }
  86. }
  87. return lol;
  88. }
Success #stdin #stdout 0.01s 27100KB
stdin
Standard input is empty
stdout
Standard output is empty