CanadianAirlines

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;

public class CanadianAirlines {
    private static ArrayList<Integer>[] graph;
    private static boolean[] used;
    private static int lengthFirstPath = 0;
    private static int answer = -1;

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("in.txt"));
        PrintWriter out = new PrintWriter(new File("out.txt"));
        int n = in.nextInt();
        int m = in.nextInt();
        graph = new ArrayList[n];
        used = new boolean[n];
        Arrays.fill(used, false);
        HashMap<String, Integer> name = new HashMap<>();
        for (int i = 0; i < n; i++) {
            name.put(in.next(), i);
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int x = name.get(in.next());
            int y = name.get(in.next());
            if (x < y) {
                graph[x].add(y);
            } else {
                graph[y].add(x);
            }
        }

        int[][] d = new int[n][n];
        for (int[] di : d) {
            Arrays.fill(di, -1);
        }
        d[0][0] = 1;
        for (Integer u : graph[0]) {
            d[0][u] = 2;
        }
        for (int a = 0; a < n; ++a) {
            for (int b = a + 1; b < n; ++b) {
                if (d[a][b] == -1) {
                    continue;
                }
                for (Integer u : graph[a]) {
                    if (u > b) {
                        d[b][u] = Math.max(d[a][b] + 1, d[b][u]);
                    } else if (u == b && u == n - 1) {
                        d[u][u] = d[a][b] + 1;
                    }
                }
                for (Integer u : graph[b]) {
                    d[a][u] = Math.max(d[a][b] + 1, d[a][u]);
                }
            }
        }

        out.println(d[n - 1][n - 1] == -1 ? "No solution" : d[n - 1][n - 1] - 1);
        out.close();
    }
}