import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Aresta {

    private Vertice verticeAdj;

    protected Vertice getVerticeAdj() {
        return verticeAdj;
    }

    protected void setVerticeAdj(Vertice verticeAdj) {
        this.verticeAdj = verticeAdj;
    }
}

class Vertice {

    private String rotulo;
    private boolean visitado;
    private List<Aresta> listaArestas;

    public Vertice() {
        this.visitado = false;
        this.listaArestas = new ArrayList<Aresta>(10);
    }

    public boolean isVisitado() {

        return this.visitado;
    }

    public String getRotulo() {
        return rotulo;
    }

    public void setRotulo(String rotulo) {
        this.rotulo = rotulo;
    }

    public List<Aresta> getListaArestas() {
        return listaArestas;
    }

    public void addAresta(Vertice rotulo) {

        Aresta a = new Aresta();
        a.setVerticeAdj(rotulo);
        ;
        this.listaArestas.add(a); // o vértice recebe esse cara
    }

    public void setVisitado() {
        this.visitado = true;

    }

    public void setNaoVisitado() {
        this.visitado = false;

    }

    @Override
    public String toString() {
        return this.getRotulo() + ",";
    }
}

class Grafo {

    private List<Vertice> listaVertices;
    static List<String> ordem = new ArrayList<>(10);
    private int cont;

    public Grafo() {
        this.listaVertices = new ArrayList<Vertice>(10);
    }

    public List<Vertice> getListaVertices() {
        return listaVertices;
    }

    public void addVertice(String rotuloVertice) {

        Vertice v = new Vertice();
        v.setRotulo(rotuloVertice);
        this.listaVertices.add(v);
    }

    public void addAresta(Grafo g, String verticeRecebeAresta, String verticeParteAresta) {

        boolean flag = false;
        boolean flag2 = false;

        int x = 0;
        for (int i = 0; i < g.getListaVertices().size(); i++) {

            if (verticeParteAresta.equalsIgnoreCase(g.getListaVertices().get(i).getRotulo())) {
                x = i;
                flag = true;
                break;
            }
        }

        int t = 0;
        for (int i = 0; i < g.getListaVertices().size(); i++) {

            if (verticeRecebeAresta.equalsIgnoreCase(g.getListaVertices().get(i).getRotulo())) {
                t = i;
                flag2 = true;
                break;
            }
        }

        if (flag && flag2) {

            g.getListaVertices().get(x).addAresta(g.getListaVertices().get(t));
            g.getListaVertices().get(t).addAresta(g.getListaVertices().get(x));

//           System.out.println("Vértice que recebeu = " + verticeRecebeAresta
//           + " "
//           + g.getListaVertices().get(t).getListaArestas());
//           System.out.println(
//           "Vértice que partiu = " + verticeParteAresta + " " +
//           g.getListaVertices().get(x).getListaArestas());
        }
    }

    void buscaLargura() {

        cont = 0;
        int aux =0;
        Queue<Vertice> fila = new LinkedList<>();

        for(int i=0;i<this.getListaVertices().size();i++){

            if(this.getListaVertices().get(i).getRotulo().equalsIgnoreCase("entrada")){
                aux = i;
                break;
            }
        }

        fila.add(this.getListaVertices().get(aux));
        this.getListaVertices().get(aux).setVisitado();

        int i = 0;
        while (!fila.isEmpty()) {

            Vertice vertice = fila.poll();

            System.out.println("Busca largura 1 Vertice = " + vertice.getRotulo());

            if (!vertice.getRotulo().equals("*")) {

                cont++;
            }

            if (vertice.getRotulo().equals("Saida")) {

                break;
            }

            i = 0;

            while (vertice.getListaArestas() != null && i < vertice.getListaArestas().size()) {

                Aresta a = vertice.getListaArestas().get(i);

                if (!a.getVerticeAdj().isVisitado()) {

                    System.out.println("Busca largura 1 Vertice adjacente = " + a.getVerticeAdj().getRotulo());

                    a.getVerticeAdj().setVisitado();
                    fila.add(a.getVerticeAdj());

                    if (a.getVerticeAdj().getRotulo().equals("*")) {

                        buscaLargura2();
                        return;
                    }
                }

                i++;
            }

            i = 0;
        }
    }

    void buscaLargura2() {

        cont = 0;
        int aux =0;


        for(int i=0;i<this.getListaVertices().size();i++){

            this.getListaVertices().get(i).setNaoVisitado();
        }

        Queue<Vertice> fila = new LinkedList<>();

        for(int i=0;i<this.getListaVertices().size();i++){

            if(this.getListaVertices().get(i).getRotulo().equalsIgnoreCase("*")){
                aux = i;
            }
        }

        fila.add(this.getListaVertices().get(aux));
        this.getListaVertices().get(aux).setVisitado();

        int i = 0;
        while (!fila.isEmpty()) {

            Vertice vertice = fila.poll();

            System.out.println("Vertice = " + vertice.getRotulo());

            if (!vertice.getRotulo().equals("Saida")) {
                cont++;
            }

            i = 0;

            while (vertice.getListaArestas() != null && i < vertice.getListaArestas().size()) {

                Aresta a = vertice.getListaArestas().get(i);

                if (!a.getVerticeAdj().isVisitado()) {

                    System.out.println("Vertice adjacente = " + a.getVerticeAdj().getRotulo());

                    a.getVerticeAdj().setVisitado();
                    fila.add(a.getVerticeAdj());

                    if (a.getVerticeAdj().getRotulo().equals("Saida")) {
                        return;

                    }
                }

                i++;
            }

            i = 0;
        }
    }


    void mostraQtdVerticesCaminhoDoRato() {

        System.out.println(this.cont);
    }

    @Override
    public String toString() {

        StringBuilder s = new StringBuilder();

        for (int i = 0; i < listaVertices.size(); i++) {

            s.append(listaVertices.get(i).getRotulo() + " Já visitado => " + listaVertices.get(i).isVisitado() + "\n");
        }
        return "Grafo = Vértices => \n" + s.toString();
    }

}

public class Main {

    public static void main(String[] args) {

        Scanner r = new Scanner(System.in);

        int qtdVertices, v = 0, qtdArestas, t;

        List<String> primeiro = new ArrayList<String>(26);
        List<String> segundo = new ArrayList<String>(26);

        Set<String> conjuntoVertices = new HashSet<>();

        qtdVertices = r.nextInt();
        qtdArestas = r.nextInt();

        Grafo grafo = new Grafo();

        t = 0;

        while (t < qtdArestas) {

            String verticeQueRecebeAresta = r.next();
            String verticeMandaAresta = r.next();

            primeiro.add(verticeQueRecebeAresta);
            segundo.add(verticeMandaAresta);

            conjuntoVertices.add(verticeMandaAresta);
            conjuntoVertices.add(verticeQueRecebeAresta);

            t++;
        }

        for(String vertice : conjuntoVertices){

            //System.out.println(vertice);
            grafo.addVertice(vertice);
        }

            //grafo.addAresta(grafo, verticeQueRecebeAresta, verticeMandaAresta);
//      }

        t = 0;
        while (t < qtdArestas) {

            grafo.addAresta(grafo, primeiro.get(t),segundo.get(t));
            t++;
        }
        grafo.buscaLargura();

        grafo.mostraQtdVerticesCaminhoDoRato();

         //System.out.println(grafo);

        r.close();
    }

}