1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Method: Graph: Floyd Warshall
* Problem: 821 - PageHopping
* Accepted: 1.080
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

public static void main(String...args)
{
Scanner scanner = new Scanner(System.in);

int m[][] = new int[101][101];
int start, end, pages = 0, caseNumber = 1, sum, links = 0;
Set<Integer> pagesSet = new HashSet<Integer>();

for(int i=1; i <= 100; i++)
for(int j=1; j <= 100; j++)
m[i][j] = 500;

while(true)
{
start = scanner.nextInt();
end = scanner.nextInt();

if(!scanner.hasNextInt())
break;

m[start][end] = 1;
pagesSet.add(start);
pagesSet.add(end);

if(start > pages)
pages = start;

if(end > pages)
pages = end;


if(start == 0 && end == 0)
{
for(int k = 1; k <= pages; k++)
for(int i = 1; i <= pages; i++)
for(int j = 1; j <= pages; j++)
if(i != j)
m[i][j] = Math.min(m[i][k] + m[k][j], m[i][j]);

sum = 0;
for(int i=1; i <= pages; i++)
for(int j=1; j <= pages; j++)
if(m[i][j] != 500)
sum += m[i][j];


links = pagesSet.size()-1;
double average = (double)sum/(links*links-links);
System.out.printf("Case %d: average length between pages = %.3f clicks\n", caseNumber++, average);

pagesSet.clear();
for(int i=1; i <= pages; i++)
for(int j=1; j <= pages; j++)
m[i][j] = 500;

pages = 0;
}
}
}
}