package qunarer;

import java.util.Scanner;
public class Main {
    public static int dijkstra(int[][] W1, int start, int end,int n) {  
        boolean[] isLabel = new boolean[n];// 是否标号  
        int[] indexs = new int[n];// 所有标号的点的下标集合，以标号的先后顺序进行存储，实际上是一个以数组表示的栈  
        int i_count = -1;//栈的顶点  
        int[] distance = W1[start].clone();// v0到各点的最短距离的初始值  
        int index = start;// 从初始点开始  
        int presentShortest = 0;//当前临时最短距离  
 
        indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
        isLabel[index] = true;  
          
        while (i_count<W1[0].length) {  
            // 第一步：标号v0,即w[0][0]找到距离v0最近的点  
 
            int min = Integer.MAX_VALUE;  
            for (int i = 0; i < distance.length; i++) {  
                if (!isLabel[i] && distance[i] != -1 && i != index) {  
                    // 如果到这个点有边,并且没有被标号  
                    if (distance[i] < min) {  
                        min = distance[i];  
                        index = i;// 把下标改为当前下标  
                    }  
                }  
            }  
            if (index == end) {//已经找到当前点了，就结束程序  
                break;  
            }  
            isLabel[index] = true;//对点进行标号  
            indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
            if (W1[indexs[i_count - 1]][index] == -1 
                    || presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {  
                // 如果两个点没有直接相连，或者两个点的路径大于最短路径  
                presentShortest = distance[index];  
            } else {  
                presentShortest += W1[indexs[i_count - 1]][index];  
            }  
 
            // 第二步：将distance中的距离加入vi  
            for (int i = 0; i < distance.length; i++) {  
                // 如果vi到那个点有边，则v0到后面点的距离加  
                if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达，则现在可达了  
                    distance[i] = presentShortest + W1[index][i];  
                } else if (W1[index][i] != -1 
                        && presentShortest + W1[index][i] < distance[i]) {  
                    // 如果以前可达，但现在的路径比以前更短，则更换成更短的路径  
                    distance[i] = presentShortest + W1[index][i];  
                }  
 
            }  
        }  
        //如果全部点都遍历完，则distance中存储的是开始点到各个点的最短路径  
        return distance[end];  
    }
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);
		Main mth=new Main();
		String firstLine=s.nextLine();
		String first[]=firstLine.split(" ", 4);
		int n=Integer.parseInt(first[0]);
		int m=Integer.parseInt(first[1]);
		String start=first[2];
		int startindex=-1;
		String end=first[3];
		int endindex=-1;
		String city="";
		String citys[]=new String[n];
		String Line[][]=new String[m][2];
		int count=0;
		for(int i=0;i<m;i++){
			String inline=s.nextLine();
			String temp[]=inline.split(" ", 2);
			for(int j=0;j<2;j++){
				Line[i][j]=temp[j];
				if(!city.contains(temp[j])){
					city=city+temp[j]+" ";
					citys[count]=temp[j];
					count++;
				}
			}
		}
//		for(int i=0;i<count;i++){
//		System.out.println(citys[i]+" ");
//		}
		//根据citys+Line构造邻接矩阵
		int mat[][]=new int[n][n];
		for(int i=0;i<n;i++){
			if(start.equals(citys[i])){
				startindex=i;
			}
			if(end.equals(citys[i])){
				endindex=i;
			}
			if(startindex!=-1 && endindex!=-1){
				break;
			}
		}
		for(int i=0;i<m;i++){
			int row=-1;
			int col=-1;
			for(int j=0;j<n;j++){
				if(Line[i][0].equals(citys[j])){
					row=j;
				}
				if(Line[i][1].equals(citys[j])){
					col=j;
				}
				if(row!=-1 && col!=-1){
					break;
				}
			}
			mat[row][col]=1;
			mat[col][row]=1;
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(mat[i][j]!=1){
					mat[i][j]=-1;
				}
				//System.out.print(mat[i][j]+"    ");
			}
			//System.out.println();
		}
		System.out.println(mth.dijkstra(mat, startindex, endindex,n));
	}
}