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

public class shortestPath
{
	public static int[][] graph;
	public static String[] names;

	public static void readGraph(String fileName) throws Exception
	{
		BufferedReader graphreader = new BufferedReader(new FileReader(fileName));
		String graphline = graphreader.readLine();
		Vector namesVec = new Vector(0,1);
		while (graphline!=null)
		{
			String[] pair =split(graphline,' ',false);
			if (pair==null) break;
			boolean exists = false;
			for (int i=0;i<namesVec.size();i++)	
			{
				if (pair[0].equals((String)(namesVec.elementAt(i))))
				{
					exists = true;
					break;
				}
			}
			if (!exists)
				namesVec.addElement(pair[0]);
			exists = false;
			for (int i=0;i<namesVec.size();i++)	
			{
				if (pair[1].equals((String)(namesVec.elementAt(i))))
				{
					exists = true;
					break;
				}
			}
			if (!exists)
				namesVec.addElement(pair[1]);
			graphline = graphreader.readLine();
		}
		int numVertices = namesVec.size();
		
		names = new String[numVertices];

		for (int i=0;i<namesVec.size();i++)	
		{
			names[i] = (String)(namesVec.elementAt(i));
		}

		graph = new int[numVertices][numVertices];
		for (int i=0;i<numVertices;i++)	
		for (int j=0;j<numVertices;j++)	
			graph[i][j]=0;
		graphreader.close();
		graphreader = new BufferedReader(new FileReader(fileName));
		graphline = graphreader.readLine();
		while (graphline!=null)
		{
			String[] pair =split(graphline,' ',false);
			if (pair==null) break;
			int ind1 = -1;
			int ind2 = -1;
			for (int i=0;i<numVertices;i++)	
			{
				if (names[i].equals(pair[0]))
				{
					ind1=i; break; 
				}
			}
			for (int i=0;i<numVertices;i++)	
			{
				if (names[i].equals(pair[1]))
				{
					ind2=i; break; 
				}
			}
			graph[ind1][ind2] = 1;
			graph[ind2][ind1] = 1;
			graphline = graphreader.readLine();
		}
	}
	
	public static int[] shortestPath(int[][] graph, String startNode)
	{
		Vector q = new Vector(0,1);
		int v;
		int numVertices = graph[0].length;
		int[] dist = new int[graph[0].length];
		boolean[] known = new boolean[graph[0].length];
		int inds = -1;
		for (int i=0;i<numVertices;i++)	
		{
			known[i]=false;
			dist[i]=-1;
		}
		for (int i=0;i<numVertices;i++)	
		{
			if (names[i].equals(startNode))
			{
				inds=i; break; 
			}
		}
		if (inds==-1)
			System.exit(1);
		q.addElement(new Integer(inds));
		dist[inds] = 0;
		while (!q.isEmpty())
		{
			v = ((Integer)q.elementAt(0)).intValue();
			q.remove(0);
			known[v] = true; 
			for (int i=0;i<numVertices;i++)	
				if (graph[v][i]==1)
					if (known[i] == false)
					{
						dist[i] = dist[v] + 1;
						q.addElement(new Integer(i));
						known[i] = true; 
					}
		}
		return dist;
	}
	
	public static void main(String[] argv) throws Exception
	{
		readGraph(argv[0]);
		System.out.println("graph reading complete "+graph[0].length);
		for (int i=0;i<graph[0].length;i++)	
		{
			for (int j=0;j<graph[0].length;j++)	
				System.out.print(graph[i][j]+" ");
			System.out.println();
		}
		String startNode = argv[1];
		int[] distances = shortestPath(graph,startNode);
		for (int i=0;i<distances.length;i++)	
		{
			System.out.println(names[i]+"\t"+distances[i]);
		}
	}

 	public static String[] split(String str, char delim, boolean zeroSizeOK)

    {
            // begin split
            Vector strsVec = new Vector(0,1);
            String tmp = str;

			if (tmp==null) return null;
            while (tmp.indexOf(delim)!=-1)
            {
             		if (zeroSizeOK || tmp.substring(0,tmp.indexOf(delim)).length()>0)
                     	strsVec.addElement(new String(tmp.substring(0,tmp.indexOf(delim))));
    	               tmp = tmp.substring(tmp.indexOf(delim)+1,tmp.length());
             }
             if (zeroSizeOK || tmp.length()>0)
             	strsVec.addElement(new String(tmp));
             String[] strs = new String[strsVec.capacity()];
             for (int s = 0; s < strsVec.capacity(); s++)
                    strs[s] = (String)strsVec.elementAt(s);
             // end of split
             return strs;
    }


}