1.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10000 - Longest Paths
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=941&mosmsg=Submission+received+with+ID+7205328
*
* @author Andre Wolfram
* @author Christoph Miesel
* @author Robert Seilbeck
* @version 1.0, 06/22/2009
*
* Status : Accepted
* Runtime 1.016
*/


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
String line;
int caseCounter = 1;
while (!(line = reader.readLine()).equals("0")) {
int n = Integer.parseInt(line);
line = reader.readLine();
int startNode = Integer.parseInt(line);

int[][] matrix = new int[n][n];
//einlesen und in adjazenzmatrix schreiben
while (!(line = reader.readLine()).equals("0 0")) {
String[] mapPair = line.split(" ");
matrix[Integer.parseInt(mapPair[0]) - 1][Integer
.parseInt(mapPair[1]) - 1] = 1;
}
//alle 0 au√�erhalb der diagonale auf "-unendlich" setzen
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][j] = -50000;
}
}
}
//diagonale auf null setzen
for (int i = 0; i < n; i++) {
matrix[i][i] = 0;
}
startNode--;
int tmp = startNode;
//floyd warshall umsetzen
for (int k = 0; k < n; k++) {
for (startNode = 0; startNode < n; startNode++) {
for (int endNode = 0; endNode < n; endNode++) {
matrix[startNode][endNode] = Math.max(
matrix[startNode][endNode],
matrix[startNode][k] + matrix[k][endNode]);
}
}
}
startNode = tmp;
int longestPath = 0;
int lastNode = 0;
//längsten pfad weglassena
for (int i = 0; i < matrix.length; i++) {
if (matrix[startNode][i] > longestPath) {
longestPath = Math.max(longestPath, matrix[startNode][i]);
lastNode = i + 1;
}
}

startNode++;
System.out.println("Case " + caseCounter
+ ": The longest path from " + startNode + " has length "
+ longestPath + ", finishing at " + lastNode + ".");
System.out.println();
caseCounter++;
}
}

}