1.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10000 - Longest Paths
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=941
*
* @author Stefan Gohlke
* @version 1.0, 12/25/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.080
*/

package longestPaths;

import java.util.Scanner;

public class Main {
public static int knotenzahl;
public static int[][] kanten;
public static int testCaseNumber;

public static void main(String[] args) {
longestPath();
}

public static void longestPath() {
testCaseNumber = 1;

Scanner scanner = new Scanner(System.in);
knotenzahl = scanner.nextInt();

while (knotenzahl != 0) {

int startPunkt = scanner.nextInt();
kanten = new int[knotenzahl + 1][knotenzahl + 1];

int x = scanner.nextInt();
int y = scanner.nextInt();

while (x > 0 && y > 0) {
kanten[x][y] = 1;
x = scanner.nextInt();
y = scanner.nextInt();
}

for (int k = 1; k <= knotenzahl; k++) {
for (int i = 1; i <= knotenzahl; i++ ) {
for (int j = 1; j <= knotenzahl; j++ ) {
if(kanten[i][k] > 0 && kanten[k][j] > 0 && kanten[i][j] < kanten[i][k] + kanten[k][j])
kanten[i][j] = kanten[i][k] + kanten[k][j];
}
}
}

int lenght = 0;
int finish = -1;

for (int i = 0; i <= knotenzahl; i++) {
if (kanten[startPunkt][i] > lenght) {
lenght = kanten[startPunkt][i];
finish = i;
}
}

if (lenght == 0) finish = startPunkt;

System.out.println("Case " + testCaseNumber
+ ": The longest path from " + startPunkt + " has length "
+ lenght + ", finishing at " + finish + ".\n");

testCaseNumber++;
knotenzahl = scanner.nextInt();
}
System.exit(0);
}
}