11463 - Commandos

#include<stdio.h>
#include<string.h>
#define M 1005

int HQ[M][M];

int main()
{
    int t,n,r,i,j,k,c,x,y;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    for(c=1;c<=t;c++)
    {
        scanf("%d%d",&n,&r);
       
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                HQ[i][j] = HQ[j][i] = M;

        for(i=0;i<n;i++)HQ[i][i] = 0;

        for(i=0;i<r;i++)
        {
            scanf("%d%d",&x,&y);
            HQ[x][y] = HQ[y][x] = 1;
        }

        for(k=0;k<n;k++)
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                {
                    x = HQ[i][k]+HQ[k][j];
                    if(x < HQ[i][j])
                        HQ[i][j] = x;
                }
        k = 0;
        scanf("%d%d",&x,&y);
        for(i=0;i<n;i++)
        {
            j = HQ[x][i]+HQ[i][y];
            if(j > k)
                k =    j;
        }

        printf("Case %d: %d\n",c,k);
    }
    return 0;
}