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


public class LOJ_Tshirt{


    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CustomType customType=new  CustomType();
        Task solver = new Task();
        solver.solve(1, in, out,customType);
        out.close();
    }


    static class Task{


        TreeMap<String,Integer> map;

        String[] str=new String[]{"XXL","XL", "L", "M", "S","XS"};


        Task()
        {
            map=new TreeMap<>();
        }







        public void solve(int testNumber, InputReader in, PrintWriter out,CustomType m) {

            for (int i = 0; i <str.length ; i++) {
                map.put(str[i],i+1);
            }







            int t=in.nextInt(),cs=1;
            while(t--!=0){

                int n=in.nextInt(), e=in.nextInt();

                EdmondsKarp ff=new EdmondsKarp(e+12);

                for (int i = 0; i <str.length ; i++) {
                    ff.addEdge(0,i+1,n);
                }


                for (int i = 0; i <e ; i++) {

                    String buff1=in.next(),buff2=in.next();
                    ff.addEdge(map.get(buff1),i+8,1);
                    ff.addEdge(map.get(buff2),i+8,1);
                    ff.addEdge(i+8,e+10,1);
                }

                long mf=ff.getMaxFlow(0,e+10);
                out.printf("Case %d: %s\n",cs++,(mf==e)?"YES":"NO");

            }




        }
    }









    static class EdmondsKarp {

        private long[][] flow;
        private long[][] capacity;
        private int[] parent;
        private boolean[] visited;
        private int n;
        EdmondsKarp(int numOfVerticles) {
            this.n = numOfVerticles;
            this.flow = new long[n][n];
            this.capacity = new long[n][n];
            this.parent = new int[n];
            this.visited = new boolean[n];
        }

        public void addEdge(int from, int to, long capacity) {
            assert capacity >= 0;
            this.capacity[from][to] += capacity;
        }

        public long getMaxFlow(int s, int t) {
            while (true) {
                final Queue<Integer> Q = new LinkedList<>();
                Arrays.fill(visited,false);
                Q.add(s);
                visited[s] = true;

                boolean check = false;
                int current;
                while (!Q.isEmpty()) {
                    current = Q.poll();
                    if (current == t) {
                        check = true;
                        break;
                    }
                    for (int i = 0; i < n; ++i) {
                        if (!visited[i] && capacity[current][i] > flow[current][i]) {
                            visited[i] = true;
                            Q.add(i);
                            parent[i] = current;
                        }
                    }
                }
                if (check == false)
                    break;

                long temp = capacity[parent[t]][t] - flow[parent[t]][t];
                for (int i = t; i != s; i = parent[i])
                    temp = Math.min(temp, (capacity[parent[i]][i] - flow[parent[i]][i]));

                for (int i = t; i != s; i = parent[i]) {
                    flow[parent[i]][i] += temp;
                    flow[i][parent[i]] -= temp;
                }
            }

            long result = 0;
            for (int i = 0; i < n; ++i)
                result += flow[s][i];
            return result;
        }
    }










    static class CustomType{
        int gcd(int a, int b)
        {
            if(a == 0 || b == 0) return a+b; // base case
            return gcd(b,a%b);
        }

        int mod (int a, int b){
            return a %b;
        }

        int[] extendedEuclid(int a,int b) {
            int[] dxy = new int[3];
            if (b ==0){
                dxy[0] =a; dxy[1] =1; dxy[2] =0;

                return dxy;
            }
            else{
                int t, t2;
                dxy = extendedEuclid(b, mod(a, b));
                t =dxy[1];
                t2 =dxy[2];
                dxy[1] =dxy[2];
                dxy[2] = t - a/b *t2;

                return dxy;
            }
        }



        int invMod(int num,int mod)
        {
            int ptr[] =extendedEuclid (num, mod);
            return ptr[1]+mod;
        }





    }


    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}