#include <stdio.h> 
#include <string.h>

#define KEY_FULL 0xFFFFFFFF

typedef struct tagDoor
{
    int nDestRoom;
    unsigned int nDoorKey;
}Door;

typedef struct tagRoom
{
    unsigned int  nKey;
    int  bVisitable;
    int  nDoorNum;
    Door nDoors[100];
}Room;


Room varpRoom[100];
char strLine[2048];

int GetNextNum(char *strLine, int *nPos)
{
    char strNum[20];
    int l = 0, k = *nPos;
    while(strLine[k] != '\0' && (strLine[k] > '9' || strLine[k] < '0'))
       k ++;
    while(strLine[k] >= '0' && strLine[k] <= '9')
    {
        strNum[l] = strLine[k];
        k ++; 
        l ++;
    } 
    *nPos = k;   
    strNum[l] = '\0';
    return atoi(strNum);
}    

int main()
{
    int N,M,i,j,k,l, nIndex, nIndex1, nIndex2, nFlag;    

    while(1)
    {
        gets(strLine);
        if(strcmp(strLine, "ENDOFINPUT") == 0) break;
        if(strcmp(strLine, "END") == 0) continue;
        k = 0;
        M = GetNextNum(strLine, &k);
        N = GetNextNum(strLine, &k);
        
        for(i = 0; i < N; i ++)
        {
            varpRoom[i].nDoorNum = 0;
            varpRoom[i].bVisitable = 0;
            varpRoom[i].nKey = 0x0;
        }
        for(i = 0; i < N; i ++)
        {
            gets(strLine);
            k = 0;
            while(strLine[k] != '\0')
            {
                while(strLine[k] != '\0' && (strLine[k] > '9' || strLine[k] < '0')) 
                   k++;

                nIndex = varpRoom[i].nDoorNum;
                varpRoom[i].nDoors[nIndex].nDestRoom = (int)(strLine[k] - '0');
                varpRoom[i].nDoors[nIndex].nDoorKey = KEY_FULL;

                nIndex1 = (int)(strLine[k] - '0');
                nIndex2 = varpRoom[nIndex1].nDoorNum;
                varpRoom[nIndex1].nDoors[nIndex2].nDestRoom = i;
                k ++;
                
                while(strLine[k] >= 'A' && strLine[k] <= 'Z')
                {
                    varpRoom[i].nDoors[nIndex].nDoorKey &= ( ~((unsigned int)1 << (strLine[k]-'A')) );
                    k ++;
                }
                varpRoom[nIndex1].nDoors[nIndex2].nDoorKey = varpRoom[i].nDoors[nIndex].nDoorKey;
                varpRoom[i].nDoorNum ++;
                varpRoom[nIndex1].nDoorNum ++;
            }
        }
        for(i = 0; i < N; i++)
        {
            gets(strLine);
            k = 0;
            while(strLine[k] != '\0')
            {
                while(strLine[k] != '\0' && (strLine[k] > 'Z' || strLine[k] < 'A')) k++;
                varpRoom[i].nKey |= ( (unsigned int)1 << (strLine[k] - 'A') );
                k ++;
            }
        }
        varpRoom[M].bVisitable = 1;

        while(!varpRoom[0].bVisitable)
        {
            nFlag = 0;
            for(i = 1; i < N; i ++)
            {
                if(!varpRoom[i].bVisitable) continue;
                for(j = 0; j < varpRoom[i].nDoorNum; j ++)
                {
                    nIndex = varpRoom[i].nDoors[j].nDestRoom;
                    if(varpRoom[nIndex].bVisitable && (varpRoom[i].nKey == varpRoom[nIndex].nKey))
                       continue; 
                    if( (varpRoom[i].nKey | varpRoom[i].nDoors[j].nDoorKey)  == KEY_FULL)
                    {
                        nFlag = 1;
                        varpRoom[nIndex].bVisitable = 1;
                        varpRoom[nIndex].nKey |= varpRoom[i].nKey;
                        varpRoom[i].nKey = varpRoom[nIndex].nKey;
                    }
                }
            }
            if(!nFlag) break;
        }
        if(varpRoom[0].bVisitable) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}