Boa noite, Felipe!
Você tem razão em notar que, dado um M>0, é possível que o programa não encontre uma rima mesmo no caso em que uma rima exista. Isso seria verdade para o M sugerido no enunciado, para 10*M ou para 1000*M. Certamente não mudaria muito o programa colocar um limitante maior, mas como se trata de parte da especificação, então minha sugestão é que você mantenha o M sugerido pelo enunciado, o que não o impede de usar valores maiores enquanto estiver depurando o EP para fins de entretenimento...
Abraços,
Marcelo