UVa 11463 - Commandos

// UVa 11463 - Commandos

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
	int tt;
	cin >> tt;
	for (int t = 1; t <= tt; t++) {
		int n, m;
		cin >> n >> m;
		int lnk[100][100];
		int cost[100][100];
		memset(lnk, 127, sizeof(lnk));
		memset(cost, 127, sizeof(cost));
		int oo = lnk[0][0];
		for (int j = 0; j < m; j++) {
			int a, b;
			cin >> a >> b;
			lnk[a][b] = 1;
			lnk[b][a] = 1;
			cost[a][b] = 1;
			cost[b][a] = 1;
		}

		// floyd
		for (int i = 0; i < n; i++)
			cost[i][i] = 0;
		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if (cost[i][k] != oo && cost[k][j] != oo && cost[i][k] + cost[k][j] < cost[i][j])
						cost[i][j] = cost[i][k] + cost[k][j];

		// sol
		int s, d;
		cin >> s >> d;
		int sol = 0;
		for (int i = 0; i < n; i++)
			if (cost[s][i] + cost[i][d] > sol)
				sol = cost[s][i] + cost[i][d];
		printf("Case %d: %d\n", t, sol);

	}
	return 0;
}