1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11792 - Krochanska is Here!
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2892
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Graphs - All shortest paths - Floyd Warshall
* Status : Accepted
* Runtime: 0.736
*/

import java.io.*;
import java.util.*;

class Main {

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

in.nextToken();
int testCases = (int)in.nval;

int stations, lines;
int pos, s, tmp, l, saveStation, saveMin, sum;
int[][] dist;

// saves the stations that appeared so far
Set<Integer> set = new HashSet<Integer>();
// saves the important stations
int[] important;

int[][] m;

Set<Integer> imp = new HashSet<Integer>();



// process test cases
for(int t = 0; t < testCases; t++)
{
in.nextToken();
stations = (int)in.nval;
in.nextToken();
lines = (int)in.nval;

// init
set.clear();
imp.clear();
saveStation = 1;
l = 0;
m = new int[lines][stations+1];
important = new int[stations+1];


// read lines and build important list
for(int ll = 0; ll < lines; ll++)
{
pos = 1;

while(true)
{
in.nextToken();
s = (int)in.nval;
if(s == 0)
break;

m[ll][s] = pos++;

if(set.contains(s))
imp.add(s);

set.add(s);
}
}

for(int i: imp)
important[l++] = i;

dist = new int[l][l];

for(int i=0; i < l; i++)
for(int j=0; j < l; j++)
if(i != j)
dist[i][j] = Integer.MAX_VALUE;

// extract distances from the lines
for(int ll = 0; ll < lines; ll++)
for(int i=0; i < l; i++)
if(m[ll][important[i]] > 0)
for(int j=0; j < l; j++)
if(i != j && m[ll][important[j]] > 0)
{
tmp = m[ll][important[i]] - m[ll][important[j]];
dist[i][j] = Math.min(dist[i][j], Math.abs(tmp));
}


// calc min distances between all pairs - floyd warshall
for(int k = 0; k < l; k++)
for(int i = 0; i < l; i++)
for(int j = 0; j < l; j++)
if(i != j && i != k && j != k)
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);


// find minimum average
saveMin = Integer.MAX_VALUE;
for(int i = 0; i < l; i++)
{
sum = 0;
for(int j = 0; j < l; j++)
sum += dist[i][j];

if(sum < saveMin || (sum == saveMin && important[i] < saveStation))
{
saveMin = sum;
saveStation = important[i];
}
}


System.out.println("Krochanska is in: " + saveStation);
}
}
}