1. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 10000 Longest Path
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=941
*
* @author Rolf Schirm
* @version 1.0, 05/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.876
*/
public class Main {

public static void main(String... args) throws Exception {
final BufferedReader scan = new BufferedReader(new
InputStreamReader(System.in));

// Queue to store elements for a possible new longest way
final Queue<Integer> queue = new LinkedList<Integer>();

// Number of the test case
int tc = 1;

String line;
while((line = scan.readLine()) != null && !line.equals("0")) {
if(!line.isEmpty()) {
// Amount of nodes
final int nodes = Integer.parseInt(line);

// Start node
final int start = Integer.parseInt(scan.readLine()) - 1;

// Indicates if a edge between two nodes exists
final boolean[][] containsWay = new boolean[nodes][nodes];

// Longest way from the start to another node
final int[] longestWay = new int[nodes];

// Clear the queue
queue.clear();

// Read the edges
while((line = scan.readLine()) != null && !line.equals("0 0")) {
String[] split = line.split(" ");
final int num1 = Integer.parseInt(split[0]) - 1;
final int num2 = Integer.parseInt(split[1]) - 1;
containsWay[num1][num2] = true;
}

// Add the start node to the queue
queue.add(start);

// Check if the queue has more elements
while(!queue.isEmpty()) {
// Take one element from the queue
int current = queue.remove();

// Check for the element if a new longest way exists
for(int i = 0; i < nodes; i++) {
// Check if a edge exists
if(containsWay[current][i]) {
// Length from start to i via current
int length = longestWay[current] + 1;

// Check if the new length is greater than the previous length
if(longestWay[i] < length) {
// Set the new longest way to i
longestWay[i] = length;

// Insert the element if its not already in the queue
if(!queue.contains(i)) {
queue.add(i);
}
}
}
}
}

// Search the maximum length
int maxValue = 0;
int maxIndex = 0;
for(int i = 0; i < nodes; i++) {
// Check if the length is greater then the current maximum
if(longestWay[i] > maxValue) {
maxValue = longestWay[i];
maxIndex = i;
}
}

// Modify the index if no path exists
if(maxValue == 0) {
maxIndex = start;
}

// Print the result
System.out.println("Case " + (tc++) + ": The longest path from " +
(start+1) + " has length " + maxValue + ", finishing at " +
(maxIndex+1) + ".");
System.out.println();
}
}
}
}