import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

class Aresta {
    private int rotulo;

    public int getRotulo() {
        return rotulo;
    }

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

    @Override
    public String toString() {
        return "Aresta [rotulo=" + rotulo + "]";
    }
}

class Vertice {

    private int 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 int getRotulo() {
        return rotulo;
    }

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

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

    public void addAresta(int rotulo) {

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

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

    }

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

class Grafo {

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

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

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

    public void addVertice(int rotuloVertice) {

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

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

        boolean flag = false;
        boolean flag2 = false;

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

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

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

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

        if (flag && flag2) {

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

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

    public void buscaProfundidade(Vertice v) {

        if (v.isVisitado() == false)
            ordem.add(v.getRotulo() + ",");

        v.setVisitado();

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

            Aresta v2 = v.getListaArestas().get(i);

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

                if (v2.getRotulo() == this.getListaVertices().get(j).getRotulo()) {

                    Vertice v3 = this.getListaVertices().get(j);

                    // System.out.println(v3);
                    if (!v3.isVisitado()) {

                        // System.out.println(v3);

                        buscaProfundidade(v3);

                    }
                }
            }
        }
    }

    // public void ordenaComponentes(){
    //
    // Collections.sort(ordem);
    //
    // for(int i=0;i<ordem.size();i++){
    //
    // System.out.print(ordem.get(i));
    // }
    //
    // ordem = new ArrayList<String>(10);
    // }

    @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) throws IOException {

        //Scanner r = new Scanner(System.in);

         BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );
        StringTokenizer tokenizer = new StringTokenizer("");

        int qtdTestes;

        tokenizer = new StringTokenizer(reader.readLine());
        qtdTestes = Integer.parseInt(tokenizer.nextToken());
        int repeticoes, v, qtdArestas, t;
        int c = 1;

        while (qtdTestes > 0) {

            Grafo grafo = new Grafo();
            v = 1;

            if (! tokenizer.hasMoreTokens() ) {
                tokenizer = new StringTokenizer(reader.readLine());
            }

            repeticoes = Integer.parseInt(tokenizer.nextToken());

            tokenizer = new StringTokenizer(reader.readLine());
            qtdArestas = Integer.parseInt(tokenizer.nextToken());

            while (repeticoes > 0) {

                grafo.addVertice(v);
                v++;

                repeticoes--;
            }

            t = 0;

            while (t < qtdArestas) {

                tokenizer = new StringTokenizer(reader.readLine());
                int verticeQueRecebeAresta = Integer.parseInt(tokenizer.nextToken());
                int rotuloAresta = Integer.parseInt(tokenizer.nextToken());

                grafo.addAresta(grafo, verticeQueRecebeAresta, rotuloAresta);
                t++;
            }

            int contComponentesConectados = 0;

            System.out.print("Caso #" + c + ": ");
            for (int j = 0; j < grafo.getListaVertices().size(); j++) {

                if (grafo.getListaVertices().get(j).isVisitado() == false) {
                    grafo.buscaProfundidade(grafo.getListaVertices().get(j));
                    // grafo.ordenaComponentes();

                    contComponentesConectados++;
                }
            }

            if (contComponentesConectados == 1) {
                System.out.println("a promessa foi cumprida");
            } else {

                contComponentesConectados--;
                System.out.println("ainda falta(m) " + contComponentesConectados + " estrada(s)");
            }
            c++;
            qtdTestes--;
        }

        //r.close();
    }
}