package problemsPackage;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class IsenbayevNumbers {
public static void main(String args[]) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int numberOfTeams = Integer.parseInt(in.readLine());
// Node containing Names of progers in team
LinkedList<String[]> teamsList = new LinkedList<String[]>();
LinkedList<String> uniqueParticipantsName = new LinkedList<String>();
while (numberOfTeams != 0) {
StringTokenizer tokenizer = new StringTokenizer(in.readLine(), " ");
String members[] = new String[3];
int i = 0;
while (tokenizer.hasMoreTokens()) {
members[i] = tokenizer.nextToken();
addToList(uniqueParticipantsName, members[i]);
i++;
}
teamsList.add(members);
numberOfTeams--;
}
int array[][] = new int[uniqueParticipantsName.size()][uniqueParticipantsName.size()];
fillArray(array,uniqueParticipantsName,teamsList);
int participants = uniqueParticipantsName.size();
int esenId = getIndex("Isenbaev", uniqueParticipantsName);
int[] tentativeDistances = new int[participants];
LinkedList<Integer>unvisitedNodes = new LinkedList<Integer>();
for(int i=0;i<participants;i++){
unvisitedNodes.add(i);
if(i==esenId) tentativeDistances[i]=0;
else tentativeDistances[i]=4000;
}
while(unvisitedNodes.size()!=0){
int node = getCurrentNode(tentativeDistances,unvisitedNodes);
processNode(node,tentativeDistances,unvisitedNodes,array);
}
String names[] = new String[uniqueParticipantsName.size()];
for(int i=0;i<uniqueParticipantsName.size();i++){
names[i]=uniqueParticipantsName.get(i);
}
java.util.Arrays.sort(names);
for(int i=0;i<names.length;i++){
int index = getIndex(names[i], uniqueParticipantsName);
int distance = tentativeDistances[index];
if(distance!=4000)
System.out.print(names[i]+" "+distance+"\n");
else System.out.print(names[i]+" undefined\n");
}
}
private static void processNode(int node, int[] tentativeDistances,
LinkedList<Integer> unvisitedNodes, int[][] array) {
LinkedList<Integer>neighbors = new LinkedList<Integer>();
for(int j=0;j<array.length;j++){
if(node!=j)
if(array[node][j]==1) neighbors.add(j);
}
for(int i=0;i<neighbors.size();i++){
if(tentativeDistances[neighbors.get(i)]>tentativeDistances[node]+1)
tentativeDistances[neighbors.get(i)]=tentativeDistances[node]+1;
}
for(int i=0;i<unvisitedNodes.size();i++){
if(unvisitedNodes.get(i)==node){
unvisitedNodes.remove(i);
break;
}
}
}
private static int getCurrentNode(int[] tentativeDistances,
LinkedList<Integer> unvisitedNodes) {
int minimum=10000;
int index=0;
for(int i=0;i<unvisitedNodes.size();i++){
if(tentativeDistances[unvisitedNodes.get(i)]<minimum){
minimum=tentativeDistances[unvisitedNodes.get(i)];
index=unvisitedNodes.get(i);
}
}
return index;
}
/**
* Fill twodimensional array
* @param array
* @param uniqueParticipantsName
* @param teamsList
*/
private static void fillArray(int[][] array,
LinkedList<String> uniqueParticipantsName,
LinkedList<String[]> teamsList) {
for(int i=0;i<uniqueParticipantsName.size();i++){
String name = uniqueParticipantsName.get(i);
for(int j=0;j<teamsList.size();j++){
boolean exist=false;
if(teamsList.get(j)[0].equalsIgnoreCase(name) || teamsList.get(j)[1].equalsIgnoreCase(name) || teamsList.get(j)[2].equalsIgnoreCase(name)) exist=true;
if(exist){
if(!teamsList.get(j)[0].equalsIgnoreCase(name)) array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[0], uniqueParticipantsName)]=1;
if(!teamsList.get(j)[1].equalsIgnoreCase(name)) array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[1], uniqueParticipantsName)]=1;
if(!teamsList.get(j)[2].equalsIgnoreCase(name)) array[getIndex(name, uniqueParticipantsName)][getIndex(teamsList.get(j)[2], uniqueParticipantsName)]=1;
}
}
}
}
/**
* Index of name in list.
* @param name
* @param uniqueParticipantsName
* @return
*/
private static int getIndex(String name,LinkedList<String> uniqueParticipantsName){
int index=0;
for(int i=0;i<uniqueParticipantsName.size();i++){
if(uniqueParticipantsName.get(i).equalsIgnoreCase(name)){
index=i;
break;
}
}
return index;
}
/**
* Store unique participant names into list
* @param uniqueParticipantsName
* @param string
*/
private static void addToList(LinkedList<String> uniqueParticipantsName,
String string) {
boolean exist = false;
for (int i = 0; i < uniqueParticipantsName.size(); i++) {
if (uniqueParticipantsName.get(i).equalsIgnoreCase(string)) {
exist = true;
break;
}
}
if (!exist)
uniqueParticipantsName.add(string);
}
}
