Q11463: Commandos

// Accepted !!

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string.h>

using namespace std;

int matrix[100][100];
void Floyd_Warshall(int n);
int imin(const int tl, const int tr);

int main()
{
    int T, N, R, u, v, s, d, index = 1;
    cin >> T;

    for(int i = 0; i < T; i++)
    {
        cin >> N >> R;

        memset(matrix, 0, sizeof(matrix));

        for(int j = 0; j < R; j++)
        {
            cin >> u >> v;
            matrix[u][v] = matrix[v][u] = 1;
        }

        Floyd_Warshall(N);

        for(int j = 0; j < N; j++)
            matrix[j][j] = 0;

        cin >> s >> d;

        int max_value = 0;

        for(int j = 0; j < N; j++)
            max_value = max(max_value, matrix[s][j] + matrix[j][d]);

        cout << "Case " << index++ << ": " << max_value << endl;
    }

    system("PAUSE");
    return EXIT_SUCCESS;
}

void Floyd_Warshall(int n)
{
     for(int k = 0; k < n; k++)
         for(int i = 0; i < n; i++)
             for(int j = 0; j < n; j++)
                 if(matrix[i][k] && matrix[k][j])
                     matrix[i][j] = imin(matrix[i][j],matrix[i][k] + matrix[k][j]);
}

int imin(const int tl, const int tr)
{
    return (tl == 0 || tl > tr)? tr : tl;
}