Problem
Amanhã Belvita abre sua padaria, mas ainda não preparou a placa do seu estabelecimento.
Belvita tem n conjuntos de comprimidos em seu armário, cada um contendo 3 comprimidos idênticos contendo exatamente duas letras latinas minúsculas.
Belvite não se importa com o nome de sua padaria, mas ela quer que o nome final contenha a substring s, que também consiste em duas letras latinas minúsculas.
Ajude Belvita a ver se é possível selecionar alguns dos tabletes disponíveis e com eles fazer o nome da padaria de forma que contenha a substring necessária.
Entrada:
A primeira linha contém duas letras latinas minúsculas - a string s que Belvita quer ver no nome da padaria.
A segunda linha contém um inteiro n (1 <= n <= 100) - o número de conjuntos de placas no armário.
As próximas n linhas contêm duas letras latinas minúsculas, cada uma descrevendo as inscrições nas tabuinhas dos conjuntos.
Saída:
Imprima "SIM" se Belvita puder escolher vários comprimidos para que a palavra resultante contenha a substring s e "NÃO" caso contrário.
Exemplos:
| Entrada |
Saída |
sim
4
ah
oi
para
ha |
SIM |
hp
2
ht
tp |
NÃO |
ah
1
ha |
SIM |
Explicações:
No primeiro exemplo, você pode usar o terceiro, segundo e primeiro conjuntos criando a palavra "tooyah" que contém a substring "ya".
No segundo exemplo, obtenha a palavra com a substring "hp" de jeito nenhum.
No terceiro exemplo, você pode usar dois dos três tabletes do primeiro conjunto, formando a palavra "haha" onde há uma substring "ah".